Ha ha ha. Okay, hang with me for a bit guys...this one gets a tad bit funny.
I'll start by showing you EXACTLY what I'm doing:
So, Fib1 is our 'recursive' model, which is a picture perfect "Tree Recursion model" in Scheme. (Those who've read through SICP are probably already laughing about a 100,000 step recursion tree...but let's see how it works.)
So, the size of the compiled binaries in Chicken are pretty similar. The total amount of code in each is pretty similar too...but:
Code: Select all
╰─$ time ./fib1
^C
[2] 2143 interrupt ./fib1
./fib1 63.66s user 0.22s system 99% cpu 1:03.97 total
╰─$ time ./fib2
./fib2 0.02s user 0.00s system 93% cpu 0.027 total
╰─$ time ./fib3
./fib3 0.03s user 0.00s system 95% cpu 0.037 total
After starting to wonder if fib1 (the tree recursive method) would EVER complete, I interrupted it. HOLY SHIT that one is a freaking resource hog. The other two are close, because they both function in linear time, and are similar. It's worth noting at this point that Chicken's CSC compiler is tail-call optimized, but that doesn't really make that much difference when the expansion of the function isn't tail-recursive.
"What the ever-loving hell?" Someone might ask. Well...it has to do with how the expansion takes place. I think that substitution makes good sense here. Essentially Fib3 has a short "dangling" tail that deals with the mutables, but is a linear method. Fib2 is a very tight linear method, and Fib1 is practically designed to eat memory. As a short example, let's look at how Fib1 would expand (fib 5)
Code: Select all
fib5 - fib 3 - fib 1 - 1
| | - fib 2 - fib 1 - 1
| | ---- fib 0 - 0
|
fib 4 - fib 2 -fib 1 - 1
| |----fib 0 - 0
|
fib 3 - fib 1 - 1
|-fib 2 -fib 1 - 1
|- fib 0 - 0
Heh, so for every step higher that 'n' is valued, our amount of processes is growing almost exponentially. Compare that to our mutable Fib3 program:
Code: Select all
fib n<--index 1---------index 2---------------index 3--->
|- a is b is 1 | - a is b is 1 | - a is b is 2
|- b is c is 1 | - b is c is 2 | - b is c is 3
|- c (+ a b) is 2 | - c (+ a b) is 3 | - c (+ a b) is 5 ...etc
(This reasoning is covered in WAY better detail in SICP, btw. Which is where I learned about most of the theory anyhow. The tree recursion example is the one used as a "Don't do this" example there. lol)
So, Fib2 & Fib3 run in a constant linear progression, while Fib1 is designed to grow until it hits a point where it can actually compress its expansion back into pure mathematical reasoning.