# Recursion Function in C/C++

## Recursion Function in C/C++

A recursion function is function that calls itself inside its definition. The execution of recursion function continues unless and until some specific condition is met to prevent its repetition. In this post we will see entire concept of recursion function in C/C++ with examples.

Every recursive solution has two major cases. They are
Base case, in which the problem is simple enough to be solved directly without making any further calls to the same function.
Recursive case, in which first the problem at hand is divided into simpler sub-parts. Second the function calls itself but with sub-parts of the problem obtained in the first step. Third, the result is obtained by combining the solutions of simpler sub-parts.

Therefore, recursion is defining large and complex problems in terms of smaller and more easily solvable problems. In recursive functions, a complex problem is defined in terms of simpler problems and the simplest problem is given explicitly.

Let’s see how recursion works

Now we will see an example to under the concept of recursion.

Eg. Write a program to calculate sum of n numbers using recursion.

## 1. Program in C:

``````//Sum of n numbers using recursion
#include<stdio.h>
int sum(int); //Function declaration or prototype
int main()
{
int n;
printf("\n Enter limit for n: ");
scanf("%d",&n);
printf("\n Sum of n numbers is : %d",sum(n)); //Function calling
return 0;
}
int sum(int n) // function definition
{
if(n==0)
return 0;
if(n>=1)
return (n+sum(n-1));
}
``````

## 2. Program in C++:

``````//Sum of n numbers using recursion
#include<iostream>
using namespace std;
int sum(int); //Function declaration or prototype
int main()
{
int n;
cout<<"\n Enter limit for n: ";
cin>>n;
cout<<"\n Sum of n numbers is : "<<sum(n); //Function calling
return 0;
}
int sum(int n) // function definition
{
if(n==0)
return 0;
if(n>=1)
return (n+sum(n-1));
}
``````

## 4. Program Parts –

1. #include is a pre-processor directive. It is used to include header files.
2.stdio/iostream is header file which has certain commands that c/c++ supports. E.g. return, main, etc.
3..h is an extension for header file.
4. void sum(int) is function name. It is user defined function. It takes an integer value as parameter.
5.int is data type. It indicates that the program returns a value.
6.main() is main function that indicates the compiler that the user written programs starts from here.
7.n is variable name.
8.print/cout is the keyword use to print a message.
9.scanf/cin is the keyword use to store values in variables.
10. sum(n) is calling function. It passes value n to function definition.
11.return statement is use to return a value. If any error occurs the program will return 0.

## 4. Explanation –

Like always the compiler checks if all necesarry header files are present or not. If yes then compilers advances to net step. In this step we declare or function (sum()). And also specify how many parameters it takes (here only one so int). In next step compiler enters main function. Here we declare an varibale ‘n’ of integer type to store the limit of n numbers. Then we ask user to enter the limit and store it in n. And finally we are calling our function. We can call our function in two ways. Either use a variable or can directly mention function name in print statement. Here we use second method. Now compiler jumps to function body.

Here in the first step we check the value of n. If it is 0 then we return 0 to the calling function. If it is not 0 then the compiler goes to the next step. Here we check if the value of n is greater than or equal to 1. If the condition is true then we add n + sum(n-1) i.e. we call our function sum with one value less than previous value. This keeps on going until the condition is false. Once the condition is false the compiler returns to the main function with the value of sum of n numbers. And finally program execution terminates.

1. It helps to reduce the size of program by minimizing the code.
2. It makes easy to maintain function calling related information.
3. Evaluation of stack can be implemented through recursion
4. Also infix, post-fix notations can be evaluated with the help of recursion.

1. It takes more time because of stack overlaping.
2. Stack overflow may occur because of recursive programs.
3. Memory requirement is more as at every recursive call, separate memory address is allocated for the variables.
4. It may lead to indefinite call if exit condition does not work.
5. Efficiency is less.

Conclusion :-

This was the concept of recursion function with examples. We hope it was clear to you. If you have any doubt just mention it in comment section below or can mail us. Do share it with your programming buddies and friends.