128 Day 5
int main()
{
int x = fib(6)
}return fib(4) + fig(5) return fib(3) + fib(4)fib(6) fib(5)return fib92) + fib(3)fib(4)
return fib(1) + fib(2)fib(3)
return fib(2) + fib(3)fib(4)return 1fib(2)return 1fib(1)return 1fib(1)return 1fib(2)
return 1fib(2)return fib(1) + fib(2)fib(3)
return 1fib(2)
return fib(1) + fib(2)fib(3)return 1fib(1)
return 1fib(2)853(^22)
23
1
11
1
1
11
1
FIGURE5.5 Returning from recursion.
In the example,nis 6 so fib(6)is called from main(). Execution jumps to the fib()
function, and nis tested for a value less than 3 on line 25. The test fails, so fib(6)
returns on line 34 the sum of the values returned by fib(4)and fib(5). Look at line 34:
return( fib(n-2) + fib(n-1));
From this return statement a call is made to fib(4)(because n == 6,fib(n-2)is the
same as fib(4)) and another call is made to fib(5)(fib(n-1)), and then the function
you are in (fib(6)) waitsuntil these calls return a value. When these return a value, this
function can return the result of summing those two values.
Because fib(5)passes in an argument that is not less than 3,fib()is called again, this
time with 4 and 3. fib(4)in turn calls fib(3)and fib(2).
The output traces these calls and the return values. Compile, link, and run this program,
entering first 1, then 2, then 3, building up to 6, and watch the output carefully.
This would be a great time to start experimenting with your debugger. Put a break point
on line 21 and then trace intoeach call to fib, keeping track of the value of nas you
work your way into each recursive call to fib.
Recursion is not used often in C++ programming, but it can be a powerful and elegant
tool for certain needs.