Recursion: Difference between revisions
(add tail call example) |
(Section on tail calls) |
||
Line 32: | Line 32: | ||
* Returns the multiplied result | * 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 | Unfortunately there's a problem with this. When we call fac we need to save our current number to the 'stack' so we can multiply it with the result of fac. If we recurse too many times we run out of memory on the stack to save our numbers. | ||
Because of this tendency to overflow the stack recursion isn't seen much in mainstream programming. | Because of this tendency to overflow the stack recursion isn't seen much in mainstream programming. | ||
Line 51: | Line 51: | ||
-- prints 2432902008176640000 | -- prints 2432902008176640000 | ||
This new code has a function 'fac' that takes a number and accumulator: | |||
- | * Returns the accumulator if the number is less than 1 | ||
* Multiplies the accumulator by the number | |||
* Calls fac with the number minus 1 and new accumulator value | |||
* Returns result of fac | |||
Instead of storing numbers on the stack and multiplying them afterwards, we now accumulate them as we go. | |||
We still have a problem. I didn't mention it earlier, but when we call functions in programming languages we also put a return address on the stack. We don't store any numbers on the stack but we still store a return address every time we call fac. If we recurse too many times we still run out of memory. | |||
We can't refactor our code here to fix this either, this is a core part of the programming language: When we call a function we want it to return back to us when it's done its work. | |||
==Tail call elimination== | |||
What if we | |||
- 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 | |||
==Loops== | ==Loops== | ||
Line 83: | Line 105: | ||
- recursion-based control flow | - recursion-based control flow | ||
==Mainstream support== | ==Mainstream support== |
Revision as of 07:50, 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 to the 'stack' so we can multiply it with the result of fac. If we recurse too many times we run out of memory on the stack to save our numbers.
Because of this tendency to overflow the stack recursion isn't seen much in mainstream programming.
Tail calls
What if we didn't need to save anything? We could recurse forever without any stack overflows.
Let's say we rewrite our factorial code to this:
function fac(n, acc) if n < 1 then return acc else return fac(n - 1, acc * n) end end print(fac(20, 1)) -- prints 2432902008176640000
This new code has a function 'fac' that takes a number and accumulator:
- Returns the accumulator if the number is less than 1
- Multiplies the accumulator by the number
- Calls fac with the number minus 1 and new accumulator value
- Returns result of fac
Instead of storing numbers on the stack and multiplying them afterwards, we now accumulate them as we go.
We still have a problem. I didn't mention it earlier, but when we call functions in programming languages we also put a return address on the stack. We don't store any numbers on the stack but we still store a return address every time we call fac. If we recurse too many times we still run out of memory.
We can't refactor our code here to fix this either, this is a core part of the programming language: When we call a function we want it to return back to us when it's done its work.
Tail call elimination
What if we
- 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
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
Mainstream support
- functional programming languages
- lua
- clang mustcall
- webassembly