Recursion: Difference between revisions
(→Mainstream support: add webassembly item) |
(→Tail call elimination: Tail call elimination note) |
||
Line 49: | Line 49: | ||
- tail call elimination | - tail call elimination | ||
- NOT an optimization, how many optimizations decide which way you can program? | |||
- hints deeper at function calls vs jumps | - hints deeper at function calls vs jumps |
Revision as of 01:33, 2 February 2022
Warning: This article is a work in progress! No refunds if it moves!
- introduction/overview
- 'magic of recursion'?
A bad example
- fibonacci example in lua
- intertwines recursive algorithm and recursion
- 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