C++ Recursion function explained using Fibonacci series

By: Emiley J Emailed: 1728 times Printed: 2337 times    

Latest comments
By: rohit kumar - how this program is work
By: Kirti - Hi..thx for the hadoop in
By: Spijker - I have altered the code a
By: ali mohammed - why we use the java in ne
By: ali mohammed - why we use the java in ne
By: mizhelle - when I exported the data
By: raul - no output as well, i'm ge
By: Rajesh - thanx very much...
By: Suindu De - Suppose we are executing

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.

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

3.
The 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.


C++ Home | All C++ Tutorials | Latest C++ Tutorials

Sponsored Links

If this tutorial doesn't answer your question, or you have a specific question, just ask an expert here. Post your question to get a direct answer.



Bookmark and Share

Comments(13)


1. View Comment

the program is writen beautifly and it is easy to understand.no difficult code is used......

View Tutorial          By: sania cheema at 2009-05-04 12:14:19
2. View Comment

i want simple program of function used in recursion,fibonacci.

View Tutorial          By: manish at 2009-05-19 01:03:19
3. View Comment

you example does not run it errors can you pls fixed it so that we can learn clearly

View Tutorial          By: dionesia at 2009-08-24 05:27:37
4. View Comment

it worked fine in solving an algorithm assingment.

View Tutorial          By: tunde bello at 2009-11-05 06:31:28
5. View Comment

Simple Codes please... I just wonder why does my program already had a value of 1 even I dont input any number...

View Tutorial          By: Joseph at 2009-11-12 05:37:50
6. View Comment

not satisfied...

want to print the fibonacci series


View Tutorial          By: nikhil jha at 2010-03-08 04:25:50
7. View Comment

for the guys who is facing problems
just change #include <iostream.h>
to #include<iostream>
and add
using namespace std;
it will work fine


View Tutorial          By: Elie at 2010-05-03 12:12:48
8. View Comment

it is very easy to understand to the learners.

View Tutorial          By: venkat at 2010-06-19 02:37:36
9. View Comment

You have clear my confusion by using simple codes!!!
Thank you


View Tutorial          By: salahu.kt at 2010-09-28 07:33:55
10. View Comment

how about this?...
#include<iostream.h>

int fibonacci(int n);

int main()
{

int number;

cout <<"Enter an integer :";
cin >> number;

for(int i=0;i<=number;i++)
{
cout <<fibonacci(i) <<" ";
}

cout << endl << endl;
for(i=0;i<=number;i++){
cout <<"Fibonacci "<< i <<" is "<< fibonacci(i) <<endl;

}
return 0;
}

int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n-1)+fibonacci(n-2);
}
}


View Tutorial          By: nadia at 2010-10-04 21:48:04
11. View Comment

my answer for this Question is :

#include <iostream>
using namespcae std;

in fib (int n)
{
if (n==0)
return 1;
else
return fib(n-1)+fib(n-2);
}


int main()
{
int x;
cout<<"please enter a number"<<endl;
cin>>x;
cout<<"The fibonacci of "<<x<<"is"<<fib(x);

return 0;
}


View Tutorial          By: Tahani at 2011-04-26 11:55:34
12. View Comment

# include <iostream.h>
void main()
{
int i,ary[10];
ary[0] = 0;
ary[1] = 1;
for(i=2;i<=9;i++)
{
ary[i] = ary[i-2] + ary [i-1] ;
}
for(i=0;i<=9;i++)
{
cout<<" "<< ary[i];
}
}


View Tutorial          By: Ali Jafar at 2011-09-18 03:47:47
13. View Comment

give me some logics for programs as soon as possible

View Tutorial          By: nari at 2011-12-07 18:28:03

Your name (required):


Your email(required, will not be shown to the public):


Your sites URL (optional):


Your comments:



More Tutorials by Emiley J
Password must include both numeric and alphabetic characters - Magento
What is Hadoop?
Returning multiple values from a web service
Tomcat and httpd configured in port 8080 and 80
Java Webservices using Netbeans and Tomcat
Java WebService connected to Database
How to Deploy a Java Web Service
Call a webservice in Java
Java WebService - Create your first web service in Java
package javax.jws does not exist
Getting Started with Android
HTML5 Location - getCurrentPosition() in HTML5
HTML5 Canvas - Using Canvas in HTML5
HTML5 - Introduction
HTML5 Video - Handling video in HTML5

More Tutorials in C++
Two-Dimensional Array Manipulation in C++
Calculate average using Two-Dimensional Array in C++
Compute the square root of the sum of the squares of an array in C++
Matrix using nested for loops in C++
Sorting an array of Strings in C++
Calculating total based on the given quantity and price in C++
Compiling and Linking Multiple Source Files in C++
Enumerations in C++
Program to add two numbers in C++
Comments in C++
while loop in C++
for loop in C++
Programming errors a compiler will detect in C++
if in C++
Using the Built-in Arithmetic Types in C++

More Latest News
Most Viewed Articles (in C++ )
Dot (.) vs Arrow (->) to access data members in C++
Calculate average using Two-Dimensional Array in C++
Public versus Private members in C++
Using cout.fill() in C++
Difference between Procedural, Structured, and Object-Oriented Programming
while (1) Loops in C++
Stray or Dangling Pointers in C++
strlen() sample program in C++
Using peek() and putback() with cin in C++
Using cout.width() in C++
Demonstrating global and local variables in C++
C++ Recursion function explained using Fibonacci series
Constructors and Destructors in C++
Classes with Other Classes as Member Data in C++
strcpy() and strncpy() sample program in C++
Most Emailed Articles (in C++)
Default arguments in C++
Matrix using nested for loops in C++
Demonstrating global and local variables in C++
Classes with Other Classes as Member Data in C++
Reverse a String in C++
Getting Started with C++
The if Statement in C++
Returning values from a function in C++
What Is a Pointer in C++?
Operator Precedence in C++
atoi(), itoa() in C++
Using cout.fill() in C++
File in C++ - Writing text to a file in C++
if in C++
Calculate average using Two-Dimensional Array in C++