Introduction to Recursive Function in C++
To start with recursive function in C++, we have already known the basic idea behind C++ functions which includes function definition to call other functions too. And this article covers the concept behind the recursive definition, a play tool concept in mathematics and programming logic. A familiar example includes factorial of a number, sum of ‘n’ natural numbers, etc. A function that calls by itself is known as Recursive function. They are just a function that is getting invoked repeatedly. Recursion has got a problem-solving tool, where it divides the larger problems into simple tasks and working out individually to follow an individual sequence.
The data structures concepts like searching, sorting, traversal of a tree make use of the recursive function for its solutions. This programming technique makes code easier. Both iteration and recursion do the same process as a repetition of the code, but the difference in recursion is they execute a specific part with the base function itself. In this article, we will discuss the recursion importance and their working process with an example in detail.
Syntax of Recursive Function in C++
The general syntax of the recursive function in c++ is given as:
return type function name([arguments])
{
Body of the statements;
function name ([actual arguments]) // recursive function
}How Recursive Function works in C++?
Recursion performs repetition on the function calls, and it stops the execution when the base case becomes true. A base case condition should be defined in the recursive function to avoid stack overflow error message. If no base case is defined it leads to infinite recursion. When a function is called it pushes them into a stack each time for the reserving resources for each repetition calls. It gives the best at tree traversal. There are two different types of recursion: Direct and indirect recursion.
Direct Recursive: Illustration
int fibn(n)
{
fib(n);
}
void main ()
{
fib(n);
}The above format is the direct recursive call where it calls immediately/ call by itself. Consider a second type called indirect recursion which involves another function call. It can be viewed in the below illustration:
Indirect Recursive: Illustration
void f(int n) {
f1();
return;
}
void f2( int n) {
f();
return;
}
void f1() {
f2();
return;
}Examples of Recursive Function in C++
In the below program you can see the execution of the program that I have provided with the default base condition. Sometimes using if-else condition in recursion helps to prevent infinite recursion. The process of the code is made with the partial solution at the intermediate and these are combined to a final solution at a tail recursion.
Example #1
Here is a simple example of a Fibonacci series of a number. The below program includes a call to the recursive function defined as fib (int n) which takes input from the user and store it in ‘n’. The next step includes taking into for loop to generate the term which is passed to the function fib () and returns the Fibonacci series. The base case is set with the if statement by checking the number =1 or 2 to print the first two values. finally, this recursive function goes on with the loop to print the series 1,1,2.
Code:
#include<iostream>
using namespace std;
int fib_r (int s)
{
if(s==1||s==2)
return 1;
else
return (fib_r(s-1) +fib_r(s-2)); // fib(n-1) + fib(n-2) for adding successive terms
}
int main ()
{
int k,n;
cout<<"Enter no.of n terms: ";
cin>>n;
cout<<" calculated fibonacci numbers are"<<endl;
for (k=1; k<=n; k++)
cout<<fib_r(k)<<endl;
return 0;
}Output:
Example #2
Checking for the palindrome number using a recursive function.
Code:
#include <iostream>
using namespace std;
int palim(int a, int t)
{
if (a == 0)
return t;
t = (t * 10) + (a % 10);
return palim(a / 10, t);
}
int main()
{
int n;
cout<<"Enter the number :"; cin>>n;
int result = palim(n, 0);
if (result == n)
cout << "Number "<<n<<" is a palindrome" << endl;
else
cout << "Number "<<n<<" is not a palindrome"<< endl;
return 0;
}Output:
Example #3
Program with a random-number generator.
Code:
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
int rand1(int n);
int main () {
int n, j;
int r;
srand(time (NULL));
cout << "Enter number of dice: ";
cin >> n;
for (j = 1; j <= n; j++) {
r = rand1(5) + 1;
cout << r << " ";
}
system("PAUSE");
return 0;
}
int rand1(int n) {
return rand () % n;
}The above program illustrates a random number generator when a dice is rolled randomly. It is performed by calling a function rand1(int n) and generates 0 to n-1 numbers. and setting seed value with null (no address). For example, if we input as 4 it throws a possibility of dice as 5,4,1,2.
Output:
There are also some concepts like linear search, common divisor and most important factorial of a given number which uses recursive implementation.
Pros of Recursion
- The code provided by them is clean and compact by simplifying the larger complex program. Uses fewer variables in the program code.
- Complex code and nested for loops are avoided here.
- Some part of the code requires backtracking which is solved recursively.
Cons of Recursion
- Takes more memory allocation due to the stack operation of all the function calls.
- It performs slower sometimes while executing the iteration process. Therefore, efficiency is less.
- It is difficult for beginners to understand the working as sometimes the code goes in-depth. if leads to out of space and causes ultimately program crashes.
Conclusion
With this, we have discussed how c++ functions work and defined recursively. And, we have gone through the correspondence and their pros and cons of recursive function in the programming world. Then we carried on by showing how it may be implemented in C++ using a recursive function definition. Further, we conclude that recursion helps in C++ to solve problems in data structure concepts like traversals, sorting and searching and can be used effectively wherever is needed.
Recommended Articles
This is a guide to Recursive Function in C++. Here we discuss how recursive function works in C++, syntax along with different examples and code implementation. You may also look at the following articles to learn more –
