Recursion In c / c++, Recursion in CPP with examples
Table of Contents
What is recursion in c/c++:
function that calls itself is known as a recursive function and this technique is known as recursion so recursion in c/c++ is basically the process of rebuilding items in a similar way and in terms of programming especially recursive functions the function gives a call to itself based on certain criteria so this enables the function to repeat itself several times outputting the result at the end of each iteration kind of like a for loop or any other looping control structure and the recursion continues until some condition is met so that it prevents infinite recursion right so in even in for loop while loop we have a condition wherein the for the control is exited outside the loop similarly in recursive functions there has to be a condition after which the recursion should stop so sometimes if-else condition is used inside okay so this was a little bit about recursive functions.
When function is called within the same function, it is known as recursion in C++. The function which calls the same function, is known as recursive function. A function that calls itself, and doesn’t perform any task after function call, is known as tail recursion.
Amazon Purchase Links:
*Please Note: These are affiliate links. I may make a commission if you buy the components through these links. I would appreciate your support in this way!
The figure below shows how recursion works by calling itself over and over again.
Example: calculate the sum of first n natural numbers so natural numbers start from 1 to infinity so I want to calculate the sum of first three numbers
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include<iostream> using namespace std; int sum(int num) { if(num !=0) return (num + sum(num-1)); else return num; } int main() { int n; cout<<”enter number: ”; cin>>n; int total = sum(n); cout<<endl<<”the sum is: ”<<n<<total<<endl; return 0; } |
Program explanation:
int sum(int num)
{
if(num !=0)
return (num + sum(num-1));
else
return num;
}
you can see we have the signature of prototype of the function. The function name is sum which is a user-defined function, its return type is integer. This function takes only one argument as the input which is also of the type integer. this is the upper limit of the numbers that you want to calculate the sum of. So if you want to calculate from one to three you simply enter three.
Inside the function you can see it’s saying if num not equal to zero that is if the number is not equal to zero then you have to return num plus sum of num minus 1. So you can see the sum is called inside the sum function itself. So this is a recursive call that is inside the sum function and calling again the sum function with a new argument which is one less than what the number. we first check if the num is equal to zero then return that number as it is, so this is that if else condition which prevents the infinite recursion in C/C++programming.
int main()
{
int n;
cout<<”enter number: ”;
cin>>n;
int total = sum(n);
cout<<endl<<”the sum is: ”<<n<<total<<endl;
return 0;
}
In the main function what I’m doing is I’m declaring an integer variable int n. Then I am saying enter number till which you want the sum of natural numbers to be calculated. Then I take the input from the user and then I created one more integer variable int total. I’ll say int total and say sum and I passed that number so if the user enters 3, I pass 3 over the function and since the recursive function returns an integer value you will see total equal to sum. So the integer value returned would be assigned to the total integer variable, that’s how return types work. So in the end, I say the sum is and the number n which entered by the user and finally, I printed out the total.
The difference between iteration and recursion in c/c++
|
Recursion |
Iteration |
| Function calls itself | Functions loops some part of code |
| Recursion is selection structure | Iteration is repetition structure |
| Recursion achieves repetition through repeated method calls | Iteration explicitly uses repetition structures |
| Recursion terminate when a base case is recognized | Iteration terminates when the loop continuation condition fail |
| Recursion invokes the function repeatedly and hence the overhead of method
calls can be costly in both processing time and memory space
|
Iteration repeatedly executes code this can be less expensive in both processor time and memory space |
| Infinite recursion occurs if the recursion step does not reduce the problem in a manner that converges on the base case | An infinite loop occurs with iteration it the loop continuation test never become false |
| Recursion returns value to the calling function | Iteration does not return value |
| Recursion make code smaller | Iteration make code longer |
| Infinite recursion can crash the system | Infinite looping uses cpu cycles repeatedly |
| Recursion is slower process | Iteration is faster. |
Example:Write a program which find the factorial of a number using recursion function
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include<iostream.h> #include<conio.h> void main() { int a; cout<<”Enter the number :”; cin>>a; cout<<”Factorial = ”<<fact(a); getch(); } long int fact(int n) { if(n==0) return(1); else return(n * fact(n-1)); } |
As this is a C++ program, as usual I started by adding the iostream.h and conio.h header files. As you know every C/C++ program has at least one function which is the main() function.
void main()
{
int a;
cout<<”Enter the number :”;
cin>>a;
cout<<”Factorial = ”<<fact(a);
getch();
}
Inside the main function, I started off by defining a variable a of the type integer. Then using the cout, I printed a message “Enter the number :” this prompts the user to enter a number which is stored in the variable a. Then finally, we print the text “Factorial=” and call the function fact(a), with the variable a passed as the argument.
long int fact(int n)
{
if(n==0)
return(1);
else
return(n * fact(n-1));
}
The function fact() is a user-defined function, its return type is long int and this function takes only one argument as the input which is of the type integer. As you can see, inside the function we have only a few lines of code which is very simply. We have an if condition which checks if the n is equal to 0, if this is true then the control will return 1 else the function will return the factorial.
I am sure, now you have the basic understanding of how recursion in C/C++ programming works.
