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.

Also read here

• what is the scope of a variable? How you define the lifetime of local and global variables in programming?
• How do you define classes and objects in C++?
• what is the switch Statement in C++?
• How many types of inheritance are here in C++?
• What are the decision making statements in C++?
• How to use rand() function in C++?
• What are the strings in C++?
• Design a matrix calculator in c++
• How to define structures in C++? What is meant by structures within structures?
• How to define and call functions in C++?
• What is the difference between if and if-else statement ?
• What is the inheritance in C++?