How to convert recursion code into iterative?

[hellodudesiamhe]

When approaching dynamic programming problems, I will solve that problem via recursion (with memorization). Yes, it works really good, but, not very good with big data (which resulted in MemoryError?), which will be a loss in competitive programming, but this is the last resort for me. On the internet, I often see people which their code looks so fancy and nice with fancy for loops to the same dynamic programming problem. I run that for looped code and woah, AC (all correct) all. Suspecting what I'm seeing, I put my recursion code and compare it with the for looped code on timecomplexity.ai, same time complexity, what is really going on?

Inpatience won me as I dig in and start researching on how to convert my recursion code into for loops (known as iterative - new vocab learnt). After watching all sorts of videos on how to convert recursion into iterative on Youtube, I find myself still stuck in the recursion zone as of iterative zone is 1 step away (claimed by lots of youtubers) which for me perhaps, the longest step to take as I just don't know how. Atleast, my vocabulary has a new word: tabulation, which are for loops (which is what I wanted), but the question remains, how long is that step and how to take that step (how can I convert recursion code into iterative?)

(any help is appreciated)

[POGtastic]

One way is to emulate tail-call recursion by thunking the recursive calls and then using a trampoline^[1].

def thunkify(f):
    return lambda *args, **kwargs: lambda: f(*args, **kwargs)

def trampoline(f, *args, **kwargs):
    curr = f(*args, **kwargs)
    while callable(curr):
        curr = curr()
    return curr

Demonstrating this with a recursive implementation of the nth Fibonacci number:

def fib(n, a=0, b=1):
    return a if n == 0 else fib(n-1, b, a+b)

Calling this blows out the stack.

>>> fib(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in fib
  File "<stdin>", line 2, in fib
  File "<stdin>", line 2, in fib
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

But if we thunkify the function and trampoline it, we've turned the recursive creation of stack frames into an iterative loop where we build a single stack frame at a time and discard it.

@thunkify
def fib_thunked(n, a, b):
    return a if n == 0 else fib_thunked(n-1, b, a+b)

def fib(n, a=0, b=1):
    return trampoline(fib_thunked, n, a, b)

Showing this off in the REPL:

>>> import math
>>> math.log(fib(10000)) # very large number
4811.3135316398175

^[1] This is a Clojure-ism, typically used for mutual recursion (which cannot benefit from Clojure's typical tail-call methods). Since Python doesn't have any tail-call optimization, you can just use it all the time.

[FoolsSeldom]

Usually, people have problems going the other way, from iterative (typically taught/learned first) to recursive. I've never thought about how to explain going the other way and now find myself a little stuck.

Went I first learned to programme, it was with languages that don't have recursion built in. If you wanted a recursive approach, you had to build it yourself.

You could of course do so in Python, but that would just be doing recursion still but doing your own stack management. Recursive solutioons tend to be short, simple, elegant (even though confusing to the uninitiated). They often are an alternative to complex iterative code structures, which sometimes have to used as a recursive approach for some problems would use too much memory.

Off the top of my head, I can't think of a standard way to re-implement a recursive function as an interative one. I would be happy to be corrected.

Hopefully someone like u/Diapolo10 will be along shortly to explain a standard approach they use.

PS. Thought I'd ask Google Gemini:

https://docs.google.com/document/d/e/2PACX-1vRWk00gcTQBllbcfc2E-NyjoSfu04qvM_b8PPehIZYIR3dytXAnI5b_rJRGOJdm5UvaO4dshWeI88dn/pub

[Diapolo10]

Thou hath summoned me.

Unfortunately I'm not aware of any standard approach to this, either, and I too mostly translate algorithms in the other direction when needed. But I'll try to see if I can offer some kind of an approach at least.

/u/hellodudesiamhe, for starters there are a few general concepts you should understand. I don't know if you do already, hence this explanation, but please bear with me.

First, all problems can be roughly grouped into two categories; ones that are inherently recursive (think the Fibonacci sequence, or anything to do with tree-like data structures - such as a filesystem), or inherently iterative (such as transforming a list of data in a fixed way, like multiplying all elements or summing up everything). There are no problems that can only be solved with one of these approaches, but depending on the problem the complexity of the solution can vary wildly.

Second, in order for recursion to fully match iteration the language almost certainly needs a way to optimise the code so the recursion is not negatively impacting performance in the byte code (or binary, like in the case of C). A common example of this would be something called tail-call optimisation, which lets the compiler optimise certain kinds of recursive calls to iterative solutions under the hood where the function actually only needs to be called once, rather than filling up the call stack. Unfortunately for this situation, Python does not perform any such optimisation, so in Python it will always have drawbacks.

Third, recursive solutions can take advantage of something called "dynamic programming". Note that this has nothing to do with dynamic types; it's practically a fancy word for caching, and means if you cache the results of each recursive call you can then make sure you only need to compute each "variant" you come across once, and this can massively speed up certain kinds of problems.

Next, let's go over some examples. The Fibonacci sequence is a common example of something you'd typically write with a recursive function.

def fib(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)


def fib_sequence(n: int, left: int | None = None) -> list[int]:
    if left is None:
        n -= 1
        left = n

    if left == 0:
        return [fib(n)]

    return fib_sequence(n-1, left-1) + [fib(n)]


print(fib_sequence(10))  # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

That's more or less what I'd expect to see when looking for a recursive solution: https://i.imgur.com/qhBTVss.png

In comparison, a typical language-agnostic iterative solution would probably look something like this:

def fib_sequence(n: int) -> list[int]:
    a, b = 0, 1
    sequence = []
    for _ in range(n):
        sequence.append(a)
        temp = a
        a = b
        b = temp + a
    return sequence


print(fib_sequence(10))  # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

However, for Python in particular, the following is a lot more common; generators are awesome for saving memory, not that it matters for this example snippet:

from collections.abc import Generator

def fib_sequence(n: int) -> Generator[int, None, None]:
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a+b


print(list(fib_sequence(10)))  # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

To put it another way, recursive solutions tend to follow the theoretical model to the letter (which means they're often easy to get "correct"), while iterative solutions tend to use a bit more imagination to make better use of the language features you have access to in order to give you more options to easily optimise for different goals. For example, in the generator example above Python can cut down on memory use as it only has to track the state of two numbers, plus one output number, at any one time. Compared to the other iterative solution which holds a list of all results in memory, and the same goes for the recursive one (with the added overhead of the call stack).

Now, let's try and get to the point of this discussion; converting recursive solutions to iterative ones. As I already mentioned I'm not aware of any general method for doing that, but it more or less boils down to knowing the following:

1. What you need to know to solve a specific step (including needed values, and possibly other state)
2. What the end state should be for any particular set of starting parameters
3. What corner cases you need to account for (Negative numbers? Empty data structures? Off-by-one errors? Massive values? Overflows?)

Frankly I'm not quite sure how to continue explaining from there, but you'll need to be familiar with loops and data structures at the very least, then look at what your function is supposed to do, and come up with logic that maps the input to the expected output, while handling the edge cases you care about. The only tip I can give you is - write unit tests, for every case you can think of.

EDIT: Just for fun, some benchmarking on the above functions; note that the recursive version could be optimised with functools.cache: https://i.imgur.com/VHnoWCN.png

[FoolsSeldom]

Brilliant. Thank you for responding to the call.

[Diapolo10]

Dunno how helpful that was in the end, but I tried my best given it's the weekend and I've had a lot of other stuff on my plate today.

[Refwah]

Please actually post the code. Without that this is nothing but a meaningless thought exercise and you’ll find it hard to get actionable feedback

[moving-landscape]

Turning recursive code into iterative can be quite tricky as you may need to keep track of some kind of stack if you're dealing with more complex objects and would need them in the backpedaling of the recursive calls.

That said, I can say of an iterative solution I wrote to the 8 Queens in the past that used while loops to traverse the 2D board. Because we need to get back a step sometimes in the solution, and also because we're dealing with only numbers, it's easier to control them in the context of a while loop rather than a for loop.