Mastering Recursion: Solving More Advanced Problems in C++

Introduction: On my day 7 of #100DaysofCode challenge, I decided to dive deeper into recursion. I took on a few more complex problems to sharpen my programming skills. Recursion is a powerful concept that can be both fascinating and challenging. In this blog, I will walk you through some intriguing recursion problems and their solutions in C++. We will explore the following examples:

1. Print Spelling Using Recursion

2. Fast Exponentiation Using Recursion

3. Power Set Using Recursion

4. Jumps - Number of Ways to Reach a Destination Using Recursion

5. Subsequence of a String Using Recursion

6. Permutation of a String

Let's dive in!

1. Print Spelling Using Recursion: Problem: Given a number, print its spelling (e.g., 123 as "one two three").

#include <iostream>
using namespace std;

void printSpelling(int n) {
    string spellings[] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    if (n == 0) return;
    printSpelling(n / 10);
    cout << spellings[n % 10] << " ";
}

int main() {
    int n;
    cin >> n;
    printSpelling(n);
    return 0;
}

2. Fast Exponentiation Using Recursion: Problem: Compute the power of a number using recursion.

#include <iostream>
using namespace std;

int power(int base, int exponent) {
    if (exponent == 0) return 1;
    int smallPower = power(base, exponent / 2);
    smallPower *= smallPower;
    if (exponent % 2 == 1) smallPower *= base;
    return smallPower;
}

int main() {
    int base, exponent;
    cin >> base >> exponent;
    cout << power(base, exponent);
    return 0;
}

3. Power Set Using Recursion: Problem: Generate the power set of a given set using recursion.

#include <iostream>
#include <vector>
using namespace std;

void generatePowerSet(vector<int>& input, vector<int>& output, int index) {
    if (index == input.size()) {
        for (int num : output) {
            cout << num << " ";
        }
        cout << endl;
        return;
    }
    // Include the current element in the set
    output.push_back(input[index]);
    generatePowerSet(input, output, index + 1);
    // Exclude the current element from the set
    output.pop_back();
    generatePowerSet(input, output, index + 1);
}

int main() {
    vector<int> input = {1, 2, 3};
    vector<int> output;
    generatePowerSet(input, output, 0);
    return 0;
}

4. Jumps - Number of Ways to Reach a Destination Using Recursion: Problem: Calculate the number of ways to reach a destination with given jump lengths.

#include <iostream>
using namespace std;

int countWaysToReachDestination(int destination, int jumpLengths[], int numJumps) {
    if (destination == 0) return 1;
    if (destination < 0) return 0;

    int totalWays = 0;
    for (int i = 0; i < numJumps; i++) {
        totalWays += countWaysToReachDestination(destination - jumpLengths[i], jumpLengths, numJumps);
    }

    return totalWays;
}

int main() {
    int destination, numJumps;
    cout << "Enter the destination and the number of jump lengths: ";
    cin >> destination >> numJumps;
    int jumpLengths[numJumps];

    cout << "Enter the jump lengths: ";
    for (int i = 0; i < numJumps; i++) {
        cin >> jumpLengths[i];
    }

    int ways = countWaysToReachDestination(destination, jumpLengths, numJumps);
    cout << "Number of ways to reach the destination: " << ways << endl;
    return 0;
}

5. Subsequence of a String Using Recursion: Problem: Find all the subsequences of a given string using recursion.

#include <iostream>
using namespace std;

void generateSubsequences(string input, string output, int index) {
    if (index == input.length()) {
        cout << output << " ";
        return;
    }

    // Include the current character
    generateSubsequences(input, output + input[index], index + 1);

    // Exclude the current character
    generateSubsequences(input, output, index + 1);
}

int main() {
    string input;
    cout << "Enter a string: ";
    cin >> input;
    generateSubsequences(input, "", 0);
    return 0;
}

6. Permutation of a String: Problem: Generate all permutations of a string using recursion.

#include <iostream>
using namespace std;

void generatePermutations(string input, int left, int right) {
    if (left == right) {
        cout << input << " ";
        return;
    }

    for (int i = left; i <= right; i++) {
        swap(input[left], input[i]);
        generatePermutations(input, left + 1, right);
        swap(input[left], input[i]); // Backtrack
    }
}

int main() {
    string input;
    cout << "Enter a string: ";
    cin >> input;
    int n = input.length();
    generatePermutations(input, 0, n - 1);
    return 0;
}

Conclusion: Recursion is a powerful technique that can be used to solve a wide range of problems. In this blog, we explored several advanced recursion problems in C++ and provided code examples to help you understand the concepts. These problems are not only challenging but also fun to solve. So, give them a try and enhance your coding skills!

#Recursion #Cplusplus #CodingChallenge #Programming