Recursion
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 restore the previous work
- You set the return value
- You jump to the previous location
This system works well in most cases.
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