Friday, October 14, 2022

Recursive and iterative nested for loops

Consider n nested for loops in Python:

for i_1 in range(n):
    for i_2 in range(n):
        for i_3 in range(n):
            ...
                for i_n in range(n):
                    doSomething()

The recursive way would be:

def nForLoops(n, depth = 0):
    if depth > n-1: doSomething()
    else:
        for i in range(n):
            nForLoops(n, depth + 1)

A simple iterative function could be written using the observation that doSomething() is called n^n times:

def nForLoops2(n, counter = 0):
    while counter < pow(n, n):
        counter += 1
        doSomething()

TODO: How could we write it iteratively using stack data structure?

No comments:

Post a Comment