What is Recursion in C++ programming language

What is Recursion in C++ programming language

Today in this blog post we will cover the concept of Recursion in C++ programming language for  beginners. So what is Recursion? And what is the use of Recursion in programming languages? We will cover the answer of these questions shortly. For now let us look at the basic introduction of Recursion. Recursion is a concept in which the function calls itself with in its own body, and breaks the complex problems into smaller and more manageable parts.

So the first question was what is recursion? Basically Recursion is a method or technique which is used in programming languages and in this method the function calls itself. It means the function is called with in its own body. We will cover this concept with simple programming example which will make the concept of recursion crystal clear to the audience.

The Second question was what is the use of Recursion in programming languages? Recursion simply breaks down complex problems or programs into smaller parts and manage them as sub-problems. So the function which calls itself is called a recursive function.

Remember one thing that a recursive function must contains,

1) Base Case

2) Recursive Case

For now just keep this thing in mind that base case is that part which stops the recursive function. And the Recursive Case is that part of the function that calls itself.

Basic Syntax of Recursive Function in C++ programming language

Syntax Example 1

int FunctionName(int parameter)
{
	if (stop_condition)
	{
		// 1) Base case (stopping condition)
		return base_value;
	}
	// 2) Recursive case (function calls itself)
	return FunctionName(modified_parameter);
}

Explanation

In the above coding example the syntax of recursive function is shown. As you can see that there is a function named as FunctionName() with data type int and this function contains a parameter. 

int FunctionName(int parameter)

Now with in this function body there is an if condition which in this function is serving as Base Case (Stopping condition). 

if (stop_condition)
{
	// 1) Base case (stopping condition)
	return base_value;
}

And after that we have second part which is the simple return statement with function name and modified parameter. This is basically the Recursive Case (Function Calling itself).

// 2) Recursive case (function calls itself)
return FunctionName(modified_parameter);

So this whole code is showing a basic syntax of recursive function in C++ programming language. If you notice in the recursive case the return statement is calling the same function FunctionName() inside its own body. So this is how the recursive basically works.

Basic Working of Recursion in C++ programming language

Now we  will look at the working of Recursive functions. The main idea behind recursion is that the recursive function calls itself in its own function body and simply breaks down the complex problems into smaller and more manageable sub-problems. Always remember that there are always two main parts of every recursive function. 

1) The first part is the base case, which serves as stopping condition and it returns value without calling the function again. And if there is no base case present in the function the program falls into infinite recursion. Now we will look at the second key component of recursive function. 

2) The second part is the recursive case this is the main part where function calls itself with modified, smaller input, moving closer to the base case.

Recursion depends on system's call stack memory. Now there are some important points to keep in mind. 

1) When a function calls itself system pushes a new stack frame which contains local variables and the return address to the memory stack.

2) The main function pauses its execution until child function finish this, we call this suspended state.

3) The step where base case executes then the function begins returning values one by one in last-in, first-out order LIFO.

4) If the function code lacks proper base case the stack runs out of memory causing segmentation fault.

Now let us look at coding example of recursion.

Simple Programming Example of Recursion in C++ programming language

Coding Example 1

#include<iostream>
#include<conio.h>
using namespace std;
int RecursiveFunction(int num)
{
	if (num > 0)
	{
		return num + RecursiveFunction(num - 1);
	}
	else
	{
		return 0;
	}
}
void main()
{
	int result = RecursiveFunction(10);
	cout << result;
	_getch();
}

Explanation

Now we are going to perform a task of adding a range of numbers together by using recursion where we will simply break this task to add two numbers at a time.

In the above coding example the name of recursive function is RecursiveFunction() with a parameter of type int num. 

int RecursiveFunction(int num)

Now if we look at this function it has an if condition which is serving as a recursive case. In this if condition we specified that if the value in num variable is greater then 0 (zero) like this

if (num > 0)
{
	return num + RecursiveFunction(num - 1);
}

Now with in this if condition the function is calling itself in the return statement as shown above. And with in this return statement we are adding num variable with RecursiveFunction(num - 1) in which we are decrementing the value of num by 1 with each function call, unless it reaches the value of 0 or less then zero. When the value in num variable reaches to 0 at that point the if condition becomes false and else part will run which is the base case 

else
{
	return 0;
}

that simply returns 0, and program comes out of RecursiveFuntion() body, and returns the calculated value to the function calling point with in the main method like this.

int result = RecursiveFunction(10);

And this 10 is the value that we initially send to RecursiveFunction() as an argument and which was stored in the num parameter of the function. So this is the working of recursive function.

Congratulations! like always we have successfully implemented recursion in C++ programming language.