Course Content
C++ Introduction
0/1
C++ Variables & Constants
0/1
C++Scope of Variable
0/1
C++ Keywords & Identifiers
0/1
C++ Data Types
0/1
C++ Basic I/O
0/1
C++ Type Conversion
0/1
C++ Operators
0/1
C++ Comments
0/1
C++ If-else
0/1
C++ Ternary Operator
0/1
C++ for Loop
0/1
C++ Ranged for Loop
0/1
C++ while/do-while Loop
0/1
C++ break Statement
0/1
C++ Continue Statement
0/1
C++ switch Statement
0/1
C++ goto Statement
0/1
C++ Functions
0/1
C++ User-defined Functions
0/1
C++ Default Arguments
0/1
C++ Storage Class
0/1
C++ Recursion
0/1
C++ Return by Reference
0/1
C++ Arrays
0/1
C++ Multi-dimentional Arrays
0/1
C++ Arrays & Function
0/1
C++ String
0/1
C++ Structure
0/1
C++ Structure & Functions
0/1
C++ Pointers to Structure
0/1
C++ Pointers
0/1
C++ Void Pointers
0/1
C++ Pointers & Arrays
0/1
C++ Pointers & Functions
0/1
C++ Dynamic Memory Allocation
0/1
C++ OOPs Concepts
0/1
C++ Objects and Class
0/1
C++ Constructors
0/1
C++ Destructors
0/1
C++ Constructor Overloading
0/1
C++ Objects & Function
0/1
C++ Enumeration
0/1
C++ Inheritance
0/1
C++ Inheritance Access Control
0/1
C++ Inheritance Types
0/1
C++ Polymorphism
0/1
C++ Function Overloading
0/1
C++ Function Overriding
0/1
C++ Operator Overloading
0/1
C++ Friend Function
0/1
C++ Virtual Function
0/1
C++ Abstract Class & Pure Virtual Function
0/1
C++ Encapsulation
0/1
C++ Abstraction
0/1
C++ Templates
0/1
C++ Exception Handling
0/1
C++ Multithreading
0/1
C++ Standard Library
0/1
C++ Programming Tutorials
About Lesson

C++ Recursion

In this article, you’ll learn about recursive function in C++ and its working with the help of examples.


Recursion

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function.

Recursion has got a problem-solving tool, where it dives the larger problems into simple tasks and wirking out individually to follow an individual sequence.


Syntax of Recursion Function

The general syntax of the recursion function in C++ is given as:

return type function name([arguments])
{
    Body of the statements;
    function name ([actual arguments])        // recursive function
}

Working of Recursion in C++

void recurse()
{
    ... .. ...
    recurse(); // function calls itself
    ... .. ...
}

int main()
{
    ... .. ...
    recurse();
    ... .. ...
}

Working

 

  • Recursion performs repetition on the function calls, and it stops the execution when the base case becomes true.
  • In Simple words, The recursion continues until some condition is met.
  • A base case condition should be defined in the recursive function to avoid stack overflow errror messages.
  • If no base case is defined it leads to infinite recursion.
  • To prevent infinite recursion, if…else statement (or similar approach) can be used where one branch makes the recursive call and the other doesn’t.

Example 1: Factorial of a Number Using Recursion

// Factorial of n = 1*2*3*...*n

#include <iostream>
using namespace std;

int fact(int);

int main() {
    int num, result;

    cout << "Enter positive number: ";
    cin >> num;

    result = fact(num);
    cout << "Factorial of " << num << " = " << result;
    return 0;
}

int fact(int num) {
    if (num > 1) {
        return num * fact(num - 1);
    } else {
        return 1;
    }
}

Output

Enter a positive number: 5
Factorial of 5 = 120

Working of Factorial Program

As we can see, the fact() function is calling itself. However, during each call, we have decreased the value of num by 1. When num is less than 1, the fact() function ultimately returns the output.


Types of recursion

There are two types of recursion

  1. Direct recursion
  2. Indirect recursion

Direct recursion

Direct recursion : When function calls itself, it is known as direct recursion.

The example, we have seen above is a direct recursion example.


Indirect recursion

Indirect recursion : When function calls another function and that function calls the calling function, then this is known as Indirect recursion.

For example : Function A calls function B and function B calls function A.


Example 2: Find Factorial using Indirect recursion

// Factorial of n = 1*2*3*...*n
#include <iostream>
using namespace std;

int factA(int);
int factB(int);

int factA(int n){
    if (n <= 1) {
        return 1;
    } else {
        return  n * factB(n - 1);
    }
}

int factB(int n){
    if (n <= 1) {
        return 1;
    } else {
        return  n * factA(n - 1);
    }
}

int main() {
    int num;

    cout << "Enter positive number: ";
    cin >> num;

    cout << "Factorial of " << num << " = " << factA(num);
    return 0;
}

Output

Enter a positive number: 5
Factorial of 5 = 120

Advantages of Recursion

  • It makes our code shorter and cleaner.
  • Recursion is required in problems concerning data structures and advanced algorithms, such as Graph and Tree Traversal.

Disadvantages of Recursion

  • It takes a lot of stack space compared to an iterative program.
  • It uses more processor time.
  • It can be more difficult to debug compared to an equivalent iterative program.
Exercise Files
No Attachment Found
No Attachment Found
error: Content is protected !!