Recursion: Difference between revisions
(Add example) |
(Dump current changes) |
||
| Line 1: | Line 1: | ||
Warning: This article is a work in progress! No refunds if it moves! | Warning: This article is a work in progress! No refunds if it moves! | ||
TODO: This article is about tail calls | |||
- introduction/overview | - introduction/overview | ||
| Line 7: | Line 9: | ||
- lua | - lua | ||
== | ==Examples== | ||
Most introductions to recursion I've seen use this Fibonacci gem: | Most introductions to recursion I've seen use this Fibonacci gem: | ||
| Line 20: | Line 22: | ||
print(fib(41)) | print(fib(41)) | ||
-- prints 165580141 | -- prints 165580141 | ||
This code is confusing | 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 | |||
function | |||
if n <= | |||
return 1 | return 1 | ||
else | else | ||
return | return n * fac(n - 1) | ||
end | end | ||
end | end | ||
print( | print(fac(20)) | ||
-- prints | -- prints 2432902008176640000 | ||
This | This looks pretty good and shows off the nature of recursion: Calling a | ||
- mention stack overflow | - mention stack overflow | ||
| Line 98: | Line 72: | ||
- recursion-based control flow | - recursion-based control flow | ||
==Tail call elimination== | ==Tail call elimination == | ||
- floating back down to reality | - floating back down to reality | ||
| Line 111: | Line 85: | ||
- structured programming, goto wars | - structured programming, goto wars | ||
==Mainstream support== | ==Mainstream support == | ||
- functional programming languages | - functional programming languages | ||
Revision as of 06:32, 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
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