A look at the difference between plain old recursion and tail recursion.
$ gdb recursion
GNU gdb (GDB) 7.2-debian
.....
(gdb)
- Set up breakpoints at recursion termination points
(gdb) break recursion.c:50
Breakpoint 1 at 0x4005b9: file /home/lmwangi/learning/algo/recursions/recursion.c, line 50.
(gdb) break recursion.c:68
Breakpoint 2 at 0x400601: file /home/lmwangi/learning/algo/recursions/recursion.c, line 68.
- Run till the first breakpoint - Good old recursion. Notice that we have to step 4 times.
(gdb) run
Starting program: /home/lmwangi/learning/algo/recursions/recursion
Breakpoint 1, factorial (n=1) at /home/lmwangi/learning/algo/recursions/recursion.c:50
50 return 1;
(gdb) bt
#0 factorial (n=1) at /home/lmwangi/learning/algo/recursions/recursion.c:50
#1 0x00000000004005cd in factorial (n=2) at /home/lmwangi/learning/algo/recursions/recursion.c:53
#2 0x00000000004005cd in factorial (n=3) at /home/lmwangi/learning/algo/recursions/recursion.c:53
#3 0x00000000004005cd in factorial (n=4) at /home/lmwangi/learning/algo/recursions/recursion.c:53
#4 0x00000000004005cd in factorial (n=5) at /home/lmwangi/learning/algo/recursions/recursion.c:53
#5 0x0000000000400544 in main () at /home/lmwangi/learning/algo/recursions/recursion.c:30
(gdb) step
56 }
(gdb) step
56 }
(gdb) step
56 }
(gdb) step
56 }
(gdb) step
56 }
(gdb) step
main () at /home/lmwangi/learning/algo/recursions/recursion.c:32
32 printf("Factorial %d\n", result);
- Tail recursion. Notice that we step only once since the function has all the results from prior operations
(gdb) cont
Continuing.
Factorial 120
Breakpoint 2, tail_factorial (n=1, a=120) at /home/lmwangi/learning/algo/recursions/recursion.c:68
68 return a;
(gdb) bt
#0 tail_factorial (n=1, a=120) at /home/lmwangi/learning/algo/recursions/recursion.c:68
#1 0x000000000040061c in tail_factorial (n=2, a=60) at /home/lmwangi/learning/algo/recursions/recursion.c:71
#2 0x000000000040061c in tail_factorial (n=3, a=20) at /home/lmwangi/learning/algo/recursions/recursion.c:71
#3 0x000000000040061c in tail_factorial (n=4, a=5) at /home/lmwangi/learning/algo/recursions/recursion.c:71
#4 0x000000000040061c in tail_factorial (n=5, a=1) at /home/lmwangi/learning/algo/recursions/recursion.c:71
#5 0x000000000040056d in main () at /home/lmwangi/learning/algo/recursions/recursion.c:34
(gdb) step
73 }
(gdb) step
main () at /home/lmwangi/learning/algo/recursions/recursion.c:36
36 printf("Tail Factorial %d\n", result);
(gdb)