Sams Teach Yourself C++ in 21 Days

Organizing into Functions 127

5

The program asks for a number to find on line 9 and assigns that number to n. It

then calls fib()with n. Execution branches to the fib()function, where, on line

23, it prints its argument.

The argument nis tested to see whether it is less than 3 on line 25; if so,fib()returns

the value 1. Otherwise, it returns the sum of the values returned by calling fib()on n-2

and n-1.

It cannot return these values until the call (to fib()) is resolved. Thus, you can picture

the program diving into fibrepeatedly until it hits a call to fibthat returns a value. The

only calls that return a value are the calls to fib(2)and fib(1). These values are then

passed up to the waiting callers, which, in turn, add the return value to their own, and

then they return. Figures 5.4 and 5.5 illustrate this recursion into fib().

Some compilers have difficulty with the use of operators in a coutstate-

ment. If you receive a warning on line 32, place parentheses around the sub-

traction operation so that lines 32 and 33 become:

std::cout << “Call fib(“ << (n-2) << “) “;

std::cout << “and fib(“ << (n-1) << “).\n”;

NOTE

ANALYSIS

int main()

{

int x = fib(6)

}

return fib(4) + fib(5) return fib(3) + fib(4)

fib(6) fib(5)

return fib(2) + fib(3)

fib(4)

return fib(1) + fib(2)

fib(3)

return fib(2) + fib(3)

fib(4)

return 1

fib(2)

return 1

fib(1)

return 1

fib(1)

return 1

fib(2)

return 1

fib(2)

return fib(1) + fib(2)

fib(3)

return 1

fib(2)

return fib(1) + fib(2)

fib(3)

return 1

fib(1)

return 1

fib(2)

FIGURE5.4 Using recursion.