8.6. Recursion
Recursive functions are a special class of functions that call themselves (also known as self-referential functions) to compute a value. Like their non-recursive counterparts, recursive functions create new stack frames for each function call. Unlike standard functions, recursive functions contain function calls to themselves.
Let’s revisit the problem of summing up the set of positive integers from
1 … n. In previous sections, we discussed the sumUp()
function to achieve this task. Table 1 shows a related function
sumDown()
which adds the numbers in reverse (n … 1) and its
recursive translation:
Iterative | Recursive |
---|---|
|
|
The base case in the recursive function sumr()
accounts for any values of n that are
less than one and the recursive step adds the current value of n to the result
of the function call to sumr()
with the value n-1. Compiling the sumr()
with
the -m32
flag and disassembling it with GDB yields the following assembly code:
0x0804841d <+0>: push %ebp # save ebp 0x0804841e <+1>: mov %esp,%ebp # update ebp (new stack frame) 0x08048420 <+3>: sub $0x8,%esp # add 8 bytes to stack frame 0x08048423 <+6>: cmp $0x0,0x8(%ebp) # compare ebp+8 (n) with 0 0x08048427 <+10>: jg 0x8048430 <sumr+19> # if (n > 0), goto <sumr+19> 0x08048429 <+12>: mov $0x0,%eax # copy 0 to eax (result) 0x0804842e <+17>: jmp 0x8048443 <sumr+38> # goto <sumr+38> 0x08048430 <+19>: mov 0x8(%ebp),%eax # copy n to eax (result) 0x08048433 <+22>: sub $0x1,%eax # subtract 1 from n (result--) 0x08048436 <+25>: mov %eax,(%esp) # copy n-1 to top of stack 0x08048439 <+28>: call 0x804841d <sumr> # call sumr() function 0x0804843e <+33>: mov 0x8(%ebp),%edx # copy n to edx 0x08048441 <+36>: add %edx,%eax # add n to result (result+=n) 0x08048443 <+38>: leave # prepare to leave the function 0x08048444 <+39>: ret # return result
Each line in the above assembly code is annotated with its English translation. Table 2 shows the corresponding goto form and C program without goto statements:
C goto form | C version without goto statements |
---|---|
|
|
While the translation above may not initially appear to be identical to the original sumr()
function, a close inspection reveals that the two functions are indeed equivalent.