Recursion
Warning: This article is a work in progress! No refunds if it moves!
- introduction/overview
- 'magic of recursion'?
- lua
Example
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 to me and to my computer. This ends up causing severe speed penalities:
- fib(38) takes 6 seconds on my computer
- fib(39) takes 10 seconds on my computer
- fib(40) takes 17 seconds on my computer
- fib(41) takes 30 seconds on my computer
fib(41) effectively takes 13 seconds to add 102334155 and 63245986 together. Ridiculous.
The issue here is that each step re-calculates all previous steps. Twice even!
An equivalent version without recursion is:
function fib(n) if n <= 1 then return 1 end a, b = 0, 1 for i = n, 1, -1 do a, b = b, a + b end return a end print(fib(41)) -- prints 165580141
This runs instantly on my machine. fib(100000000) takes 6 seconds on my computer.
At this point the impression you would get is that recursion is slow and ill suited for these tasks. Not so fast!
We can modify the example to store the previous two steps in the 'a' and 'b' function arguments:
function fib(n, a, b) if n <= 1 then return b else return fib(n - 1, b, a + b) end end print(fib(41, 0, 1)) -- prints 165580141
This version is just as fast as the iterative solution, it's just written recursively.
- 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