Recursion in C++

In a C programming language, a function that calls itself is known as a recursive function.

And, this technique is called as recursion. 

Recursive functions are very useful to solve many problems such as  Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc.

How recursion works?

void recurse()
	{
 	   ... .. ...
  	  recurse();
  	  ... .. ...
	}

	int main()
	{
   	 ... .. ...
   	 recurse();
   	 ... .. ...
	}

Example: Write a program in a C++ language to find the factorial using recursion.

#include 

using namespace std;
int factorial(int n);

int main() {
        int n;
        cout << "Enter a number to find factorial: ";
        cin >> n;
        cout << "\nFactorial of " << n << " is= " << factorial(n);
        return 0;
}
int factorial(int n) {
        if (n >= 1)
                return n * factorial(n - 1);
        else
                return 1;
}

Output

Enter a number to find factorial: 
5				// enter by user
Factorial of 5 =  120

Example: Write a program in a C language to print the Fibonacci series using recursion.

Fibonacci series are 0, 1, 1, 2, 3, 5, 8, …,. 

In fibonacci series, except for the first two terms of the series, every other term is the sum of the previous two terms, for example, 5 = 2 + 3.

#include 

using namespace std;
int fibonacci(int);

int main() {
        int n, i = 0, c;
        cout << "Enter the nth number in fibonacci series ";
        cin >> n;

        cout << "\n Fibonacci series terms are:\n";

        for (c = 1; c <= n; c++) {
                cout << " " << fibonacci(i);
                i++;
        }

        return 0;
}

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

Output

Enter the nth number in fibonacci series 
7		// enter by user
 Fibonacci series terms are:
0  1  1  2  3  5  8   13   21   34
Categories C++