String Recursion

Last week, we learned that recursion is a powerful programming technique, and we used it to solve numerical problems: finding the nth Fibonacci number, calculating the factorial function, etc. This week, we will use recursion on lists and strings to solve more complex problems.

Just like numerical recursion, string recursion involves breaking down a problem into smaller subproblems and solving them recursively. We can think of strings as collections of n characters, and can make the problem smaller at each step by solving a problem of size n - 1, then solving a problem of n - 2, etc., all the way down to a base case.

In this lesson, we will explore three common applications of string recursion in Python: printing a string, finding the length of a string, and appending a character to a string.

Printing a String

Let's use recursion to print a string, one character at a time. Thinking recursively, we can define the problem of printing a string as follows:

print(string of length n) = print(one character), then print(string of length n - 1)

Here's a recursive function that does this:

def print_string(s):
    if len(s) == 0:
        return
    else:
        print(s[0])
        print_string(s[1:])

Notice a few things:

• The base case occurs when the function is given the empty string (''). In that case, there's nothing left to print, so we can simply return.
• We make a recursive call to print_string() with everything but the first character using a slice, s[1:].
• The function has no return value. Recursive functions may or may not have a return value. In this case, print_string() can accomplish its task without returning a specific value.

Finding the length of a string

Watch the following video to learn how to write a recursive function that calculates the length of a string.

In contrast to print_string() above, the recursive_str_len() function that was written in the video returns a number. This return value is built up through the return statements in the series of recursive calls.

Replacing a character in a string

Watch the following video to see how to write a recursive function that replaces a character in a string.

Efficiency

Note that for each of the above examples -- printing a string, finding the length of a string, and replacing characters in a string -- we needed to recurse over the length of the string. This is analogous to using a for loop to iterate over the characters of the string. Therefore, all three of these algorithms are O(n).