Table of Contents

Introduction

How to implement recursion in C++? Explain with an example There are certain cases where it is necessary a function calls itself. Such types of functions are called recursive functions. This call can be direct or indirect. Recursive functions usually divides the actual problem into two parts: the first or simpler case is called the base case. It usually knows how to solve the simple part. If the function is called with the base case it usually returns a value. But if the problem is little complex, then as mentioned above program knows how to solve the simple part and little bit about the complex part. But this complex part should resemble with the simple part to some extent. So while implementing the recursion, the function launches a fresh copy of itself to work on the smaller problem. This is called the recursive call and also known as the recursion step. The keyword return must be included with the recursion step because its result will be merged with the main problem.

Recursion steps keeps executing while the original function has not yet stopped executing. As function keeps dividing the original problem into subproblems, the recursive step keeps calling. For terminating this recursive call, each time the function calls itself with a slightly simpler version of original problem, this sequence of smaller and smaller problems must eventually converge on the base case.

Example

Factorial of a number using recursion

The best way to understand the recursion concept is to implement the factorial of an non-negative integer.

int fact (int n)

{
if (n==0)

return 1;

else }

return n*fact(n-1);

}

so if n=0 then the answer is computed in a simple step. But if n>0 then the function calls itself for calculating the factorial of a number n.

Recursion is more expensive in terms of storage and time as compared to looping structures.

Fibonacci Series using recursion

Another example of recursion is the implementation of Fibonacci series. The Fibonacci series begins with 0 and 1 and the next numbers are the summation of two subsequent Fibonacci numbers.

0,1,1,2,3,5,8,13,21,32,………..

code for implementing Fibonacci numbers in C++

int fib(int n)

{
if((n==0)||(n==1))

return n;

else

return fib(n-1)+fib(n-2);

}

void main()

{

clrscr();

for(int i=0;i<=10;i++)

cout<<fib(i)<<endl;

}

this program will print first 10 Fibonacci numbers.

2 thoughts on “How to implement recursion in C++? Explain with an example”

Pingback: what is the scope of a variable in programming? local variables and global variables examples
Pingback: What are the random numbers in C++? How to use rand() function for generating random numbers?