Search⌘ K
AI Features
Home
Courses
Recursion for Coding Interviews in C++

Changing Iterative Code to Recursive

Explore how to convert iterative code into recursive functions by identifying loops, setting base cases, and passing parameters. This lesson helps you understand the step-by-step transformation process using practical C++ examples to improve your coding and interview skills.

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. The code below shows the two types of code followed by an explanation.

Print all Distinct Letters

Given a string, the code must print all the distinct letters, in the order that they appear. The two implementations of the same code are shown below. First, look through the two codes and spot the differences and then read the explanation to better understand the transformation process.

Iterative
Recursive
#include <iostream>
#include <string>
using namespace std;
int main(){
  
  string name="Hello Worldd";
  //The first for loop which iterates over every character
  for(int i=0; i<name.length(); i++){
    int duplicate=0;
    char current = name[i];
    // The second for loop which removes all other duplicate occurences
    for(int j=i+1; j<name.length(); j++){
    
      if(current==name[j]){
      //Removing the duplicate occurence
        duplicate = 1;
        name= name.substr(0,j) + name.substr(j+1,name.length()-1);
      }
    }
    if(duplicate==0){
    cout<<current<<endl;
    }
  }
}

Transforming the Code

  • The first step is to identify the loop in the iterative code. This loop has two features;
    • It will modify a variable
    • At the end it will give you an output

In this code, look at lines 10 to 24. This encompasses the two loops in our case, and the cout statement, which is our output. Note that the modification happens in the loop from lines 14 to 21, so this is the loop that we deal with.

  • The loop that contains the modification is then transferred into a function outside the main body, and becomes the function body, as shown in lines 11 to 15 in the recursive code.

  • The second step is that the condition in this loop then becomes the base case of the function defined.

Look at line 14 in the iterative code; it sets j to a value of 1 greater than the index and then continues until it reaches the length of name. This is the same way the base case on line 8 checks if the index passed is equal to the length of name and terminates if it is.

  • The third step is to pass the local variables as input parameters to the function for modification.

Here, note that not just the string name is passed to the function when it is declared on line 6, but also an integer index is passed. This is meant to help replace the outer for loop in the iterative code and make the implementation recursive.

  • The index is passed to the function print, and the function can now recursively call upon itself. It does this by simply incrementing the index by 1 in each call, as it does on line 20. Once the string reaches a point where the base case is met, it will terminate. This eliminates the need for the outer for loop.

  • The last step, is that before the recursive call you must print the letter at the index. This is done before the recursive call, because the recursive call simulates the outer for loop in the iterative code, and in this case the cout is written before the next “iteration” or now, the next call.

Note: Had this function returned a variable or a value, that would have been written after or within the recursive call, as a return statement shows the end of the function. This you will see in the following chapters!

Now that we know what recursion is, how to write recursive code, the differences between recursion and iteration and its advantages and disadvantages, let’s look at practical examples of recursion in numbers!