Organizing into Functions 1255
An algorithm is a set of steps you follow to solve a problem. One algorithm for the
Fibonacci series is the following:- Ask the user for a position in the series.
- Call the fib()function with that position, passing in the value the user entered.
- The fib()function examines the argument (n). If n < 3it returns 1 ; otherwise,
fib()calls itself (recursively) passing in n-2. It then calls itself again passing in n-
1 , and returns the sum of the first call and the second.
If you call fib(1), it returns 1. If you call fib(2), it returns 1. If you call fib(3),it
returns the sum of calling fib(2)and fib(1). Because fib(2)returns 1 and fib(1)
returns 1 ,fib(3)returns 2 (the sum of 1 + 1).
If you call fib(4), it returns the sum of calling fib(3)and fib(2). You just saw that
fib(3)returns 2 (by calling fib(2)and fib(1)) and that fib(2)returns 1 , so fib(4)
sums these numbers and returns 3 , which is the fourth number in the series.
Taking this one more step, if you call fib(5), it returns the sum of fib(4)and fib(3).
You’ve seen that fib(4)returns 3 and fib(3)returns 2 , so the sum returned is 5.
This method is not the most efficient way to solve this problem (in fib(20)the fib()
function is called 13,529 times!), but it does work. Be careful—if you feed in too large a
number, you’ll run out of memory. Every time fib()is called, memory is set aside.
When it returns, memory is freed. With recursion, memory continues to be set aside
before it is freed, and this system can eat memory very quickly. Listing 5.10 implements
the fib()function.
When you run Listing 5.10, use a small number (less than 15). Because this
uses recursion, it can consume a lot of memory.CAUTION
LISTING5.10 A Demonstration of Recursion Using the Fibonacci Series
1: // Fibonacci series using recursion
2: #include <iostream>
3: int fib (int n);
4:
5: int main()
6: {
7:
8: int n, answer;
9: std::cout << “Enter number to find: “;
10: std::cin >> n;
11: