Recursion In c / c++, Recursion in CPP with examples

(Last Updated On: April 12, 2020)

recursion in c

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.


The figure below shows how recursion works by calling itself over and over again.

recursion in c

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



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

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.

Recommended For You

About the Author: Engr Fahad

My name is Shahzada Fahad and I am an Electrical Engineer. I have been doing Job in UAE as a site engineer in an Electrical Construction Company. Currently, I am running my own YouTube channel "Electronic Clinic", and managing this Website. My Hobbies are * Watching Movies * Music * Martial Arts * Photography * Travelling * Make Sketches and so on...

Leave a Reply