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