From recursive to iterative functions (step by step)

Published on Tuesday 8 November 2022

Tags: recursion2 iteration2 algorithm3 python7

From recursive to iterative functions (step by step)

Recursive and iterative algorithms are two ways of solving problems. A recursive algorithm calls itself repeatedly until it reaches a base case, while the iterative one uses a loop to repeat operations until a condition is met. Both can achieve the same results but have different advantages and disadvantages. In this article, we will see how to turn a recursive into an iterative function step-by-step.

Table of Content

Step 0: Write your recursive function

Step 1: Wrap the function’s body into a while loop

Step 2: Initialize the result variable before the loop

Step 3: Turn the special cases "return" into break or continue statements

Step 4: Replace the function name with result variable

Step 5: Turn the final “return” into an update statement

Step 6: Return the result variable

Step 7 (Optional): Refactor your code.

What about more complex algorithms?

Step #0: Write your recursive function

def factorial(n):
    if n==1 or n==0:
        return 1
    return n*factorial(n-1)

Step #1: Wrap the function’s body into a while loop

def factorial(n):
    while True:
        if n==1 or n==0:
            return 1
        return n*factorial(n-1)

Step #2: Initialize the result variable before the loop

def factorial(n):
    result = 1
    while True:
        if n==1 or n==0:
            return 1
        return n*factorial(n-1)

Step #3: Turn the special cases "return" into break or continue statements

def factorial(n):
    result = 1
    while True:
        if n==1 or n==0:
            break
        return n*factorial(n-1)

Step #4: Replace the function name with result variable

def factorial(n):
    result = 1
    while True:
        if n==1 or n==0:
            break
        return n*result(n-1)

Step #5: Turn the final “return” into an update statement

def factorial(n):
    result = 1
    while True:
        if n==1 or n==0:
            break
        result, n = n*result, n-1

Step #6: Return the result variable

def factorial(n):
    result = 1
    while True:
        if n==1 or n==0:
            break
        result, n = n*result, n-1
    return result

Step #7 (Optional): Refactor your code.

def factorial(n):
    result = 1
    while n!=1 and n!=0:
        result, n = n*result, n-1
    return result

def factorial(n):
    for i in range(n-1,0,-1):
        n *= i
    return n if n!=0 else 1

What about more complex algorithms?

Unfortunately, it's not always that simple. There are cases in which we need to perform several operations on differently modified versions of the input parameters. Still, obtaining the iterative algorithm is possible by following these principles:

Initialize a queue (list) of tuple, where each tuple contain the starting input paramenters.
Iterate over and "consume" this queue using a while loop, until it's empty.
Determine stop/continue and result's update conditions within the loop.
Append new tuples if stop/continue conditions are not met.

Read this post if you want a concrete example about that.