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
Examples
Most introductions to recursion I've seen use this Fibonacci gem:
function fib(n) if n <= 1 then return n else return fib(n - 1) + fib(n - 2) end end print(fib(41)) -- prints 165580141
This code is confusing and slow. You'd never see anyone actually use this code, so as far as I'm concerned it's not a real example. If I didn't know better, I'd think this is a ploy to make recursion look bad.
A better example is this factorial code:
function fac(n) if n <= 0 then return 1 else return n * fac(n - 1) end end print(fac(20)) -- prints 2432902008176640000
This looks pretty good and shows off the nature of recursion: Calling a
- mention stack overflow
- imagine an infinite stack
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
Tail call elimination
- floating back down to reality
- 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
Mainstream support
- functional programming languages
- lua
- clang mustcall
- webassembly