Converting Iterative Code to Recursive Code

In this lesson, we will learn how to convert an iterative code to recursive code.

We'll cover the following

The key to transforming iterative code to recursive code is to find the specific lines of code that get transformed between the two implementations. Let’s have a look at an example:

Steps for Converting Iterative Code to Recursive

  1. Identify the main loop
    • This loop should be modifying one or more variables
    • It should return a result based on the final values.
  2. Use the loop condition as the base case and the body of the loop as the recursive case.
  3. The local variables in the iterative version turn into parameters in the recursive version.
  4. Compile and rerun tests.
  5. Refactor the new function: You may be able to remove some temps, and find a better structure for the conditional in the recursive function

Let’s have a look at an example:

Reverse a String

By reversing we simply mean, we can take the string and flip it. All the letters in the front, go to the back and vice versa.

String reversal
String reversal

The codes below show the two implementations: iterative and recursive method of reversing a string.

Notice the differences in the code yourself before looking at the explanation:

def reverseString(string):
  reverse = ''
  length = len(string) - 1
  while length >= 0:
    reverse = reverse + string[length]
    length = length - 1
    
  return reverse
# Driver Code
targetVariable = "Educative"
print(reverseString(targetVariable))
Iterative method for reversing a string

Explanation

  • Step 1: Identify the loop in the iterative code (line number 5-7). This loop has two features;
    • It will modify a variable
    • At the end, it will give you an output

Analyse the iterative code. In each iteration, the last letter of the input string is being added to another string reverse. Then iterator length for the input string is reduced.

  • Step 2(a): Convert the loop condition length >= 0 to base case for recursive code.

    • This can be done by analyzing what will be the situation for the last iteration, i.e, the iteration where any further iterations will stop.
    • In our case the last condition will be length == 0. So this will be our base case.

  • Step 2(b): Convert the body of the loop to recursive case.

    • In the iterative version we are appending the last letter of input string to the beginning of a new string reverse and decreasing the length of input string.
    • Now, we will perform this recursively, i.e., reverseString(string[1:]) + string[0].
    • Here, we are passing the decreased string to the function reverseString but appending the first letter to the end of the string.

  • Step 3: Here, we can skip step 3 because there are no major local variables. The variable reverse in our code, just stores the result. We don’t need to pass this as input parameter.

  • Step 4 and 5: Perform any modifications if required to get the desired output.

In the coming lessons of this chapter, we will be looking at both the iterative and recursive method of solving a problem. This will help you get into the groove of solving problems with recursion for the later chapters.