Why convert?
Recursive methods of accomplishing a task are often more intuitive than iterative methods. If you have iterative code and don’t understand what it’s doing, it can be helpful to convert this code into a recursive function instead.
Greatest Common Divisor (Example):
The following iterative code is supposed to find the greatest common divisor of a and b, but it might be hard to understand why this works. So, we’ll turn it into a recursive function.
int a = 72, b = 20; while (a != b) { if (a > b) a -= b; else if (b > a) b -= a; } System.out.println("GCD: " + a);
The iterative code has local variables a and b, which will ultimately determine the answer. These variables become the parameters of the recursive function, while the answer itself will be returned by the function. So far, the recursive function is this:
public static int gcd(int a, int b) { // Code to find the gcd return gcd }
Note: The return statement simply indicates that the gcd will be returned, but it doesn’t have parameters yet (the parameters will be added soon).
In the iterative code, the loop is repeated until the condition (a != b) becomes False, which means it will execute until a equals b. This means that (a == b) is the base case, and when this base case is reached, the iterative code just prints a. So, the recursive function should return a when the base case is reached:
public static int gcd(int a, int b) { // Base case if (a == b) return a; // Code to find the gcd return gcd }
The iterative code uses if/else statements to determine which local variables to modify. This means the recursive function should use the same if/else statements to determine which parameters to modify (remember: we turned the variables in the iterative code into parameters in the recursive function).
For example, if (a > b), then the loop is executed again with a = a - b. Translating this to the recursive function, we simply call the function again with parameters (a - b, b) instead of (a, b). The opposite is true if (b > a). The final recursive function becomes this:
public static int gcd (int a, int b) { // Base case if(a == b) return a; else if(a > b) return gcd(a-b, b); else return gcd(a, b-a); }
This code is also much easier to interpret than the original iterative code. (As an exercise, take a look at it and figure out why this method of finding the gcd works.)
General Method:
In general, to convert from iterative to recursive:
- Turn the loop into a function, where the local variables become parameters and the final answer becomes the return statement.
- The base case occurs when the loop condition of the iterative code becomes false.
- Determine how the local variables are modified in the loop, and use a similar structure to modify the parameters and make the next recursive call in your function.
Converting from a recursive function back to iterative code can be more complicated, depending on the complexity of the recursive function. However, in most cases, the same steps as above can be applied in the opposite direction.
Practice
Negative Sum
Implement the iterative code as a recursive function to clarify what the algorithm does.
Copyright © 2021 Code 4 Tomorrow. All rights reserved.
The code in this course is licensed under the MIT License.
If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.