Recursion in C++

Recursion in C++


What is Recursion ?

Recursion is the process in which a function calls itself directly or indirectly. And the function that calls itself is known as a recursive function. 

How recursion works ?

Basic Structure of Recursion :

void recursion()
{
	recursion();
}
int main()
{
	recursion();
}

We all know that a C++ program terminates from main( ) function, similarly here main( ) function calls the recursion( ) function in very first step and then the recursion( ) function calls itself again. All kind of Recursion functions works in this similar way.

A Recursion Program :


//c++ program to calculate
//sum of natural numbers recursively

#include<iostream>
using namespace std;

int sum(int n) 
{
	if (n != 0)
		return n + sum(n-1);	
		// sum() function calls itself
	else
		return n;
}

int main()
{
	int num, result;

	cout << "Enter a positive integer : ";
	cin >> num;

	result = sum(num); 
	//sum() function is called by main() function

	cout << "Sum of first " << num << " numbers : " << result;
	
	return 0;
}

Output ~


Direct & Indirect Recursion :

Direct Recursion ~
A function is called direct recursive if it calls the same function itself.

void directFunction()
{
	directFunction();
}

Indirect Recursion ~
A function is called indirect recursive function if it calls another and the called function calls the previous function directly or indirectly.

void indirectFunction1()
{
	indirectFunction2();
}

void indirectFunction2()
{
	indirectFunction1();
}


Key Points about Recursion : 

  • ~ While using recursion in a function, programmers need to be careful to define an exit condition from the function, otherwise it will go into an infinite loop.
  • ~ Recursive program takes more space than usual iterative programs.
  • ~ Recursive program takes much time as it calls function many times and returns the value.