Recursion: Difference between revisions
(fix wording) |
(Add function calls) |
||
Line 9: | Line 9: | ||
- lua | - lua | ||
- lambdas, etc | |||
== Function calls== | |||
Let's look at a hypothetical hello world program: | |||
function | function main() | ||
value = 0 | |||
print("Hello world!") | |||
return value | |||
end | end | ||
The main function does two things here: | |||
* | *Creates a variable with the value 0 | ||
* Calls | *Calls the print function with the value "Hello world!" | ||
* | * Returns with the value of the variable | ||
Calling a function is fairly easy: | |||
* You save your work and current location | |||
* You set the function's arguments | |||
* You jump to the beginning of the function | |||
Returning from a function is just as easy: | |||
* You set the return value | |||
* You restore the previous work | |||
* You jump to the previous location | |||
==Function calls== | |||
==Tail | == Tail calls== | ||
== Tail call elimination == | |||
What if we | What if we | ||
Revision as of 03:06, 3 February 2022
Warning: This article is a work in progress! No refunds if it moves!
TODO: This article is about tail calls
- introduction/overview
- 'magic of recursion'?
- lua
- lambdas, etc
Function calls
Let's look at a hypothetical hello world program:
function main() value = 0 print("Hello world!") return value end
The main function does two things here:
- Creates a variable with the value 0
- Calls the print function with the value "Hello world!"
- Returns with the value of the variable
Calling a function is fairly easy:
- You save your work and current location
- You set the function's arguments
- You jump to the beginning of the function
Returning from a function is just as easy:
- You set the return value
- You restore the previous work
- You jump to the previous location
Function calls
Tail calls
Tail call elimination
What if we
- we've been writing code as there's no stack
- tail call elimination
- NOT an optimization, how many optimizations decide which way you can program?
- hints deeper at function calls vs jumps
- structured programming, goto wars
Loops
- recursion can implement loops!
- implementing a for loop
- implementing a while loop
- implementing a do while loop
- each loop iteration only shares global and function args
State machines
- implementing a stateful algorithm
- some kind of menu system
- the code makes sense to read
- this is mutual recursion
- very hard to do in a traditional structured language
Lambdas
- lambdas to actually replace looping constructs/switch statements
- most mainstream languages support lambas
- recursion-based control flow
Mainstream support
- functional programming languages
- lua
- clang mustcall
- webassembly