Recursion: Difference between revisions

From JookWiki
m (Jookia moved page Recursion to Tail calls without leaving a redirect: New topic)
(Write most of the recursion section)
Line 9: Line 9:
- lua
- lua


==Examples==
==Recursion==
Most introductions to recursion I've seen use this Fibonacci gem:
As a quick refresher, recursion is when code calls itself.


function fib(n)
Here's a textbook example:
  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)
  function fac(n)
   if n <= 0 then
   if n < 1 then
     return 1
     return 1
   else
   else
Line 37: Line 25:
  -- prints 2432902008176640000
  -- prints 2432902008176640000


This looks pretty good and shows off the nature of recursion: Calling a
This code has a function 'fac' that takes a number and:
 
* Returns 1 if the number is less than 1
* Calls fac with the number minus 1
* Multiplies the result of fac by the number
* Returns the multiplied result
 
Unfortunately there's a problem with this. When we call fac we need to save our current number so we can multiply it with the result of fac. If we recurse too many times we run out of memory on our stack to save our numbers.
 
Because of this tendency to overflow the stack recursion isn't seen much in mainstream programming.


- mention stack overflow
- mention stack overflow  


- imagine an infinite stack
- imagine an infinite stack

Revision as of 06:58, 2 February 2022

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

Recursion

As a quick refresher, recursion is when code calls itself.

Here's a textbook example:

function fac(n)
  if n < 1 then
    return 1
  else
    return n * fac(n - 1)
  end
end

print(fac(20))
-- prints 2432902008176640000

This code has a function 'fac' that takes a number and:

  • Returns 1 if the number is less than 1
  • Calls fac with the number minus 1
  • Multiplies the result of fac by the number
  • Returns the multiplied result

Unfortunately there's a problem with this. When we call fac we need to save our current number so we can multiply it with the result of fac. If we recurse too many times we run out of memory on our stack to save our numbers.

Because of this tendency to overflow the stack recursion isn't seen much in mainstream programming.

- 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