Find the Length of the String Using Recursion

Problem Statement

Calculate the length of a string using the recursion.

Examples

Example 1

Input: String = “TheJat”
Output: Length of the string  = 6

Theory

To calculate the length of a string using recursion, we can follow these steps:

1. Base Case: If the string is empty, return 0.
2. Recursive Step: Ignore the first character of the string and call the function recursively with the rest of the string.
3. Addition: Add 1 to the length obtained from the recursive call.

Different Approaches

1️⃣ Recursion

stringLength("hello")
                |
                | return 1 + stringLength("ello")
                | 
    stringLength("ello")
                |
                | return 1 + stringLength("llo")
                | 
        stringLength("llo")
                |
                | return 1 + stringLength("lo")
                | 
            stringLength("lo")
                |
                | return 1 + stringLength("o")
                | 
                stringLength("o")
                |
                | return 1 + stringLength("")
                | 
                        stringLength("")
                |
                | return 0
                | 

Code Implementation in C++

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

// Function to calculate the length of a string using recursion
int stringLength(string str) {
    // Base case: if the string is empty, return 0
    if (str == "")
        return 0;
    
    // Recursive step: ignore the first character and call the function recursively with the rest of the string
    return 1 + stringLength(str.substr(1));
}

int main() {
    string str = "TheJat";

    cout << "Length of the string \"" << str << "\" is " << stringLength(str) << endl;

    return 0;
}

Output

Length of the string "TheJat" is 6

Explanation:

• In this implementation, we recursively calculate the length of the string by ignoring the first character and calling the function recursively with the rest of the string.
• When the string becomes empty, we return 0.
• Otherwise, we return 1 + stringLength(str.substr(1)), which adds 1 to the length obtained from the recursive call.

Complexity Analysis:

• Time Complexity:O(n)
  • Since each character of the string is visited once.
• Space Complexity:O(n)
  • Due to the recursion stack, which can go as deep as the length of the string.