Alright, I finally solved this for myself and anyone else who may have been baffled by QuantumPete's wizardry.
Using:
Code:
#include <stdio.h>
int fib (int num, char *side) {
int x=-1, y=-1;
printf("fib: %d %s\n", num, side);
if (num <= 2) {
printf("done %s\n", side);
return 1;
}
x=fib(num-1,"X"); y=fib(num-2,"Y");
printf("x: %d y: %d %s\n", x, y, side);
return x+y;
}
int main (int argc, char *argv[]) {
printf("answer: %d\n", fib(atoi(argv[1]), "start"));
}
./a.out 5
Code:
fib: 5 start calculation of fib(5)
fib: 4 X recursion for X: fib(5-1)
fib: 3 X recursion for x of X: fib(4-1)
fib: 2 X recursion for x of x of X: fib(3-1)
done X equals 2, return 1 for x of X.
fib: 1 Y y of x of X
done Y ...will be 1
x: 1 y: 1 X so x of X is 2
fib: 2 Y
done Y and y of X is 1
x: 2 y: 1 X so X will be 3
fib: 3 Y recursion for Y: fib(5-2)
fib: 2 X recursion for x of Y: fib(3-1)
done X is 2, so return 1
fib: 1 Y recursion for y of Y: fib(3-2)
done Y returns 1 also
x: 1 y: 1 Y so Y will be 2
x: 3 y: 2 start
answer: 5 okay!
No wonder it takes so long -- it's essentially adding 1+1+1+1+1+1...