AppDividend
Latest Code Tutorials

C++ Recursion Example | Recursion Program In C++ Tutorial

0

C++ Recursion Example | Recursion Program In C++ Tutorial is today’s topic. When a function calls itself, it is known as recursion. The function which calls the function itself is known as a recursive function. The main aim of recursion is to break a bigger problem into a smaller problem. Base case solutions are usually provided, and then we express the solution of the bigger problem in terms of that base case solution step by step. It is essential to add a base case because if we don’t add a base case recursion will never stop.

C++ Recursion Example

Recursion is a process in which the function calls itself directly or indirectly is called recursion, and the corresponding function is called the recursive function. Using a recursive algorithm, certain problems can be solved quite easily. Examples of such problems are the Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc.

#What is the base condition in recursion

In recursive program, the solution to a base case is provided, and a to stop it.solution to the bigger problem is expressed in terms of smaller problems.

int fact(int n)
{
    if (n < = 1) // base case
        return 1;
    else    
        return n*fact(n-1);    
}

In the above example, a base case for n < = 1 is defined and a larger value of the number can be solved by converting to a smaller one till the base case is reached.

The recursion continues until some condition is met to stop it.

If we want to prevent an infinite recursion, if…else statement (or similar approach) can be used where one branch makes a recursive call, and others don’t.

#How can we particular problem is solved using the recursion

The idea is to represent the problem in terms of one or more smaller problems, and add one or more base conditions that stop a recursion.

For example, we compute factorial the n if we know the factorial of (n-1). The base case for the factorial would be n = 0. We return 1 when n = 0.

There are two types of recursions.

  1. Direct Recursion
  2. Indirect Recursion

#Direct Recursion

When the function calls itself, it is called direct recursion.

#Indirect Recursion

When the function calls another function, and that function calls back the first function, then we call it an indirect recursion.

 For example, function A calls the function B, and Function B calls the function A.

#Syntax of recursive functions

return_type   function_name
{
     function_name();
}
int main()
{
     function_name();
}

#Fibinacci Series Program using recursion in C++

Write a program to print Fibonacci series using recursion in C++.

#include <iostream>
using namespace std;
void fib(int);
int main()
{
  int n;
  cout << "Program to print the fibonacci series\n";
  cout << "\nEnter the number of terms:";
  cin >> n;
  fib(n);
  return 0;
}

void fib(int n)
{
  int a = 0, b = 1, c, i;
  cout << "\n";
  cout << "\t" << a << "\t" << b;
  for (i = 3; i <= n; i++)
  {
    c = a + b;
    cout << "\t" << c;
    a = b;
    b = c;
  }
}

See the following output.

 

C++ Recursion Example

#Factorial number using recursion in C++

See the following program.

#include <iostream>
using namespace std;
int rec(int);

main()
{
  int a, fact;
  cout << "Enter the number:";
  cin >> a;
  fact = rec(a);
  cout << "\nFactorial of a number:" << fact;
}
int rec(int x)
{
  int f;
  if (x == 1)
    return (1);
  else
    f = x * rec(x - 1);
  return (f);
}

See the following output.

 

Factorial number using recursion in C++

Suppose the user entered 5, which is passed to the rec() function.

  1. In the first rec() function, test expression inside if statement is true. The return (f) statement is executed, which calls the second rec() function and argument passed is x-1, which is 4.
  2. In the second rec() function, test expression inside if statement is true. The return (f) statement is executed, which calls the third rec() function and argument passed is x-1, which is 3.
  3. In the third rec() function, test expression inside if statement is true. The return (f) statement is executed, which calls the fourth function, and the argument passed is x-1, which is 2.
  4. In the fourth rec() function, test expression inside if statement is true. The return (f) statement is executed, which calls the fourth function, and the argument passed is x-1, which is 1.
  5. In the fifth rec() function, test expression inside if statement is false. The return 1 statement is executed.
  6. So, that is how we get the 5*4*3*2*1 = 120.

Finally, C++ Recursion Example | Recursion Program In C++ Tutorial is over.

Leave A Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.