Back to: C++ Tutorial

A function that calls itself is called a recursive function. A recursive function must definitely have a condition that exits from calling the function again. hence there must be a condition that calls the function itself if that condition is true.if the condition is false then it will exit from the loop of calling itself again.

The function actually knows how to solve only the simplest case or so-called base case. If the function is called with a base case, the function simply returns a result. If the function is called with a more complex problem, the function divides the problem into two conceptual pieces a piece that the function knows how to do and a piece that the function does not how to do.

**1.Example of recursive function** **in C++**

```
#include<iostream>
using namespace std;
int main()
{
int factorial(int);
int fact,value;
cout<<"Enter any number: ";
cin>>value;
fact=factorial(value);
cout<<"Factorial of a number is: "<<fact<<endl;
return 0;
}
int factorial(int n)
{
if(n<0)
return(-1); /*Wrong value*/
if(n==0)
return(1); /*Terminating condition*/
else
{
return(n*factorial(n-1));
}
}
Output:
Enter any number: 5
Factorial of a number is: 120
```

__Fibonacci Series using Recursion__

The Fibonacci series is 0,1,1,2,3,5,8,13,21…..

begins with 0 and 1and has the property that each subsequent Fibonacci number is the sum of the previous two Fibonacci numbers.

The series occurs in nature and, in particular, describes a form of a spiral. The ratio of successive Fibonacci numbers converges on a constant value of 1.618… This number, too. repeatedly occurs in nature and has been called the golden ratio or the golden mean. Humans tend to find the golden means aesthetically pleasing. Architects often design windows, rooms, and buildings whose length and width are in the ratio of the golden mean Postcards are often designed with a golden mean length/width ratio

The Fibonacci series can be defined recursively as follows:

Fibonacci(0)=0

Fibonacci(1)=1

Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2)

**2.Displaying Fibonacci series in C++ using recursion**

#include<iostream> using std::cout; using std::cin; using std::endl; unsigned long fibonacci(unsigned long); int main() { unsigned long result,number; cout<<"Enter an integer"; cin>>number; result=fibonacci(number); cout<<"Fibonacci("<<number<<")="<<result << endl; return 0; } unsigned long fibonacci(unsigned long n) { if(n==0||n==1) return n; else return fibonacci(n-1)+fibonacci(n-2); }

### OUTPUT:

Enter an integer:2 Fibonacci(2)=1

__Recursion vs Iteration__

Both iteration and recursion are based on a control structure: Iteration uses a repetition structure; recursion uses a selection structure. Both iteration and recursion involve repetition: Iteration explicitly uses a repetition structure; recursion achieves repetition through repetition function calls. Iteration and recursion both involve a termination test: Iteration terminates when the loop-continuation condition fails; recursion terminates when a base case is recognized. Iteration with counter-controlled repetition and recursion both gradually approach termination: Iteration modifies a counter until the counter assumes a value that makes the loop-continuation condition fail; recursion produces simpler versions of the original problem until the base case is reached. Both iteration and recursion can occur infinitely: An infinite loop occurs with iteration if the loop-continuation test never becomes false; infinite recursion occurs if the recursion step does not reduce the problem during each recursive call in a manner that converges in the base case.

Recursion has many negatives. It repeatedly invokes the mechanism and consequently the overhead, of a function calls. This can be expensive in both processor time and memory space. Each recursive call causes another copy of the function to be created; this can consume considerable memory. Iteration normally occurs within a function, so the overhead of repeated function calls and extra memory assignment is omitted.