## C++ Recursion function explained using Fibonacci series

**By:** Emiley J in C++ Tutorials on 2007-09-04

A function can call itself. This is called recursion, and recursion can be direct or indirect. It is direct when a function calls itself; it is indirect recursion when a function calls another function that then calls the first function.

Some problems are most easily solved by recursion, usually those in which you act on data and then act in the same way on the result. Both types of recursion, direct and indirect, come in two varieties: those that eventually end and produce an answer, and those that never end and produce a runtime failure. Programmers think that the latter is quite funny (when it happens to someone else).

It is important to note that when a function calls itself, a new copy of that
function is run. The local variables in the second version are independent of
the local variables in the first, and they cannot affect one another directly,
any more than the local variables in `main()` can affect the local
variables in any function it calls, as was illustrated in Listing 5.4.

To illustrate solving a problem using recursion, consider the Fibonacci series:

1,1,2,3,5,8,13,21,34...

Each number, after the second, is the sum of the two numbers before it. A Fibonacci problem might be to determine what the 12th number in the series is.

One way to solve this problem is to examine the series carefully. The first two numbers are 1. Each subsequent number is the sum of the previous two numbers. Thus, the seventh number is the sum of the sixth and fifth numbers. More generally, the nth number is the sum of n - 2 and n - 1, as long as n > 2.

Recursive functions need a stop condition. Something must happen to cause the program to stop recursing, or it will never end. In the Fibonacci series, n < 3 is a stop condition.

The algorithm to use is this:

**1.**Ask the user for a position in the series.

Call the

2.`fib()`function with that position, passing in the value the user entered.

The

3.`fib()`function examines the argument (`n`). If`n < 3`it returns 1; otherwise,`fib()`calls itself (recursively) passing in`n-2`, calls itself again passing in`n-1`, and returns the sum.

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)` will return `2`.

If you call `fib(4)`, it returns the sum of calling `fib(3)`
and `fib(2)`. We've established that `fib(3)` returns `2`
(by calling `fib(2)` and `fib(1)`) and that `fib(2)`
returns `1`, so `fib(4)` will sum these numbers and return `3`,
which is the fourth number in the series.

Taking this one more step, if you call `fib(5)`, it will return the
sum of `fib(4)` and `fib(3)`. We've established that `fib(4)`
returns `3` and `fib(3)` returns `2`, so the sum returned
will be `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. Sample program below implements the `fib()`
function.

WARNING:When you run this program, use a small number (less than 15). Because this uses recursion, it can consume a lot of memory.

**Demonstrates
recursion using the Fibonacci series****.**

1: // Demonstrates recursion 2: // Fibonacci find. 3: // Finds the nth Fibonacci number 4: // Uses this algorithm: Fib(n) = fib(n-1) + fib(n-2) 5: // Stop conditions: n = 2 || n = 1 6: 7: #include <iostream.h> 8: 9: int fib(int n); 10: 11: int main() 12: { 13: 14: int n, answer; 15: cout << "Enter number to find: "; 16: cin >> n; 17: 18: cout << "\n\n"; 19: 20: answer = fib(n); 21: 22: cout << answer << " is the " << n << "th Fibonacci number\n"; 23: return 0; 24: } 25: 26: int fib (int n) 27: { 28: cout << "Processing fib(" << n << ")... "; 29: 30: if (n < 3 ) 31: { 32: cout << "Return 1!\n"; 33: return (1); 34: } 35: else 36: { 37: cout << "Call fib(" << n-2 << ") and fib(" << n-1 << ").\n"; 38: return( fib(n-2) + fib(n-1)); 39: }40: }Output: Enter number to find: 5 Processing fib(5)... Call fib(3) and fib(4). Processing fib(3)... Call fib(1) and fib(2). Processing fib(1)... Return 1! Processing fib(2)... Return 1! Processing fib(4)... Call fib(2) and fib(3). Processing fib(2)... Return 1! Processing fib(3)... Call fib(1) and fib(2). Processing fib(1)... Return 1! Processing fib(2)... Return 1! 5 is the 5th Fibonacci number

**Analysis:**** **The program asks for a
number to find on line 15 and assigns that number to `target`. It then
calls `fib()` with the `target`. Execution branches to the `fib()`
function, where, on line 28, it prints its argument.

The argument `n` is tested to see whether it equals `1` or `2`
on line 30; if so, `fib()` returns. Otherwise, it returns the sums of the
values returned by calling `fib()` on `n-2` and `n-1`.

In the example, `n` is 5 so `fib(5)` is called from `main()`.
Execution jumps to the `fib()` function, and `n` is tested for a
value less than 3 on line 30. The test fails, so `fib(5)` returns the sum
of the values returned by `fib(3)` and `fib(4)`. That is, `fib()`
is called on `n-2` (5 - 2 = 3) and `n-1` (5 - 1 = 4). `fib(4)`
will return `3` and `fib(3)` will return `2`, so the final
answer will be 5.

Because `fib(4)` passes in an argument that is not less than 3, `fib()`
will be called again, this time with 3 and 2. `fib(3)` will in turn call `fib(2)`
and `fib(1)`. Finally, the calls to `fib(2)` and `fib(1)`
will both return `1`, because these are the stop conditions.

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. Then, just for fun, try the number 20. If you don't run out of
memory, it makes quite a show!

Recursion is not used often in C++ programming, but it can be a powerful and
elegant tool for certain needs.

### Add Comment

This policy contains information about your privacy. By posting, you are declaring that you understand this policy:

- Your name, rating, website address, town, country, state and comment will be publicly displayed if entered.
- Aside from the data entered into these form fields, other stored data about your comment will include:
- Your IP address (not displayed)
- The time/date of your submission (displayed)

- Your email address will not be shared. It is collected for only two reasons:
- Administrative purposes, should a need to contact you arise.
- To inform you of new comments, should you subscribe to receive notifications.

- A cookie may be set on your computer. This is used to remember your inputs. It will expire by itself.

This policy is subject to change at any time and without notice.

These terms and conditions contain rules about posting comments. By submitting a comment, you are declaring that you agree with these rules:

- Although the administrator will attempt to moderate comments, it is impossible for every comment to have been moderated at any given time.
- You acknowledge that all comments express the views and opinions of the original author and not those of the administrator.
- You agree not to post any material which is knowingly false, obscene, hateful, threatening, harassing or invasive of a person's privacy.
- The administrator has the right to edit, move or remove any comment for any reason and without notice.

Failure to comply with these rules may result in being banned from submitting further comments.

These terms and conditions are subject to change at any time and without notice.

- Data Science
- Android
- React Native
- AJAX
- ASP.net
- C
- C++
- C#
- Cocoa
- Cloud Computing
- HTML5
- Java
- Javascript
- JSF
- JSP
- J2ME
- Java Beans
- EJB
- JDBC
- Linux
- Mac OS X
- iPhone
- MySQL
- Office 365
- Perl
- PHP
- Python
- Ruby
- VB.net
- Hibernate
- Struts
- SAP
- Trends
- Tech Reviews
- WebServices
- XML
- Certification
- Interview

#### categories

#### Related Tutorials

Calculating total based on the given quantity and price in C++

Sorting an array of Strings in C++

Matrix using nested for loops in C++

Compute the square root of the sum of the squares of an array in C++

Calculate average using Two-Dimensional Array in C++

Two-Dimensional Array Manipulation in C++

Compiling and Linking Multiple Source Files in C++

Escape Sequences for Nonprintable Characters in C++

Using the Built-in Arithmetic Types in C++

## Comments