• +91-9142290450

  • Hajipur, Bihar, 844101

☰
❮
❯

C++ Recursion

← Previous Next →

What is Recursion in C++?

Recursion in C++ is a programming technique where a function calls itself directly or indirectly to solve a problem. It is one of the most powerful concepts in computer programming because it helps in breaking down complex problems into smaller, simpler subproblems. Each recursive call processes a smaller portion of the task until a base condition is met that stops further calls.

Recursion is often used in problems like calculating factorials, generating Fibonacci series, reversing strings, traversing trees, and solving mathematical puzzles like the Tower of Hanoi.

How Recursion Works

A recursive function typically has two main components:

  1. Base case: The condition that stops the recursion from continuing infinitely.

  2. Recursive case: The part of the function where it calls itself with a modified argument.

If a recursive function does not have a base case, it can lead to infinite recursion and eventually cause a stack overflow error.

Here’s the basic structure of a recursive function in C++:

void functionName() {
    // Base case
    if (condition)
        return;

    // Recursive call
    functionName();
}

The base case ensures that the recursion ends at a certain point, preventing the program from calling itself endlessly.

Example: Simple Recursion

Let’s start with a simple example that prints numbers from 1 to 5 using recursion.

#include <iostream>
using namespace std;

void printNumbers(int n) {
    if (n == 0)
        return;
    printNumbers(n - 1);
    cout << n << " ";
}

int main() {
    printNumbers(5);
    return 0;
}

Explanation:

  • The function printNumbers() calls itself with a smaller value of n.

  • When n becomes 0, the base case stops further recursive calls.

  • As the recursive calls return, the numbers are printed in ascending order.

Output:

1 2 3 4 5

Example: Factorial Using Recursion

The factorial of a number n (written as n!) is the product of all positive integers less than or equal to n.

Formula:

n! = n × (n-1) × (n-2) × ... × 1

Let’s calculate this using recursion:

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n == 0 || n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

int main() {
    int num = 5;
    cout << "Factorial of " << num << " is " << factorial(num);
    return 0;
}

Explanation:

  • The base case checks if n is 0 or 1, returning 1 in that case.

  • Otherwise, the function multiplies n with the factorial of n-1.

Output:

Factorial of 5 is 120

Types of Recursion in C++

There are mainly two types of recursion in C++:

1. Direct Recursion

When a function directly calls itself, it’s known as direct recursion.

Example:

void example() {
    example(); // Direct recursion
}

2. Indirect Recursion

When a function calls another function, which in turn calls the first function, it’s known as indirect recursion.

Example:

#include <iostream>
using namespace std;

void A(int);
void B(int);

void A(int n) {
    if (n > 0) {
        cout << n << " ";
        B(n - 1);
    }
}

void B(int n) {
    if (n > 1) {
        cout << n << " ";
        A(n / 2);
    }
}

int main() {
    A(10);
    return 0;
}

Here, A() calls B(), and B() calls A(), creating an indirect recursive relationship.

Example: Fibonacci Series Using Recursion

The Fibonacci sequence is a famous example of recursion. Each number is the sum of the two preceding ones:

0, 1, 1, 2, 3, 5, 8, ...

Here’s how you can implement it using recursion:

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int terms = 7;
    cout << "Fibonacci Series: ";
    for (int i = 0; i < terms; i++) {
        cout << fibonacci(i) << " ";
    }
    return 0;
}

Output:

Fibonacci Series: 0 1 1 2 3 5 8

Tail Recursion

Tail recursion is a special kind of recursion where the recursive call is the last operation in the function. This type of recursion can be optimized by the compiler to avoid excessive stack usage.

Example:

#include <iostream>
using namespace std;

void printNumbers(int n) {
    if (n == 0)
        return;
    cout << n << " ";
    printNumbers(n - 1); // last statement - tail recursion
}

int main() {
    printNumbers(5);
    return 0;
}

Explanation:
Here, after printing the number, the function calls itself. Since there’s nothing left to do after the recursive call, this is tail recursion.

Head Recursion

In head recursion, the function makes the recursive call before executing any other statement.

Example:

#include <iostream>
using namespace std;

void printNumbers(int n) {
    if (n == 0)
        return;
    printNumbers(n - 1);
    cout << n << " ";
}

int main() {
    printNumbers(5);
    return 0;
}

Explanation:
In this case, the function first calls itself before printing. As a result, numbers are printed in ascending order.

Common Uses of Recursion

Recursion is used in various areas of computer science and algorithms:

  • Factorial calculation

  • Fibonacci sequence generation

  • Binary search

  • Tree traversal (preorder, inorder, postorder)

  • Graph traversal (DFS)

  • Solving puzzles like Tower of Hanoi

  • String reversal and palindrome checking

Advantages of Recursion

  • Simplifies complex problems by breaking them into smaller subproblems.

  • Reduces code size compared to iterative solutions.

  • Useful in solving problems with repetitive structures like trees and graphs.

Disadvantages of Recursion

  • Consumes more memory due to multiple function calls stored in the call stack.

  • Slower performance compared to iterative solutions.

  • Risk of stack overflow if the base condition is missing or incorrect.

Summary of C++ Recursion

  • Recursion means a function calling itself to solve a problem step by step.

  • Every recursive function must have a base case to stop infinite calls.

  • Types include direct recursion, indirect recursion, head recursion, and tail recursion.

  • Common applications include factorial, Fibonacci, and searching/traversing algorithms.

  • While recursion simplifies logic, it must be used carefully to avoid performance issues.

Practice Questions

  1. Write a recursive function to find the factorial of a given number.

  2. Create a recursive function to calculate the nth Fibonacci number.

  3. Write a recursive function to print numbers from 1 to N in ascending order.

  4. Write a recursive function to print numbers from N to 1 in descending order.

  5. Create a recursive function to find the sum of digits of a given number.

  6. Write a recursive function to calculate the power of a number (x^y).

  7. Create a recursive function to find the greatest common divisor (GCD) of two numbers.

  8. Write a recursive function to reverse a given string.

  9. Create a recursive function to check if a string is a palindrome.

  10. Write a recursive function to find the sum of all elements in an array.

← Previous Next →

Try a Short Quiz.

coding learning websites codepractice

No quizzes available.

CPP Programming

online coding class codepractice

Introduction to C++

C++ Basics

Control Flow

Collections & Memory

Functions

Object-Oriented Programming

File Handling & Date

Error Handling & Validation

STL & Data Structures

Namespaces

codepractice logo
Login
Go Back Top