Recursion

From JookWiki
Revision as of 06:32, 2 February 2022 by Jookia (talk | contribs) (Dump current changes)

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