Converting a function with two recursive calls into an interative function

Question

I've got a function that has two recursive calls and I'm trying to convert it to an iterative function. I've got it figured out where I can do it with one call fairly easily, but I can't figure out how to incorporate the other call.

the function:

def specialMultiplication(n):
    if n < 2:
        return 1
    return n * specialMultiplication(n-1) * specialMultiplication(n-2)

If I just had one of them, it would be really easily:

def specialMult(n, mult = 1):
    while n > 1: 
        (n, mult) = (n-1, n * mult) # Or n-2 for the second one
    return mult

I just can't figure out how to add the second call in to get the right answer overall. Thanks!

Your algorithm's running time is exponential. Whether you implement it recursively or iteratively will only change the running time by a constant factor. — merlin2011, Dec 31 '16 at 22:26
Thanks @merlin2011. I see that now. Just trying to figure out how to convert it to a dynamic style. — firelover, Dec 31 '16 at 22:37
Blckknght's answer is a DP solution which should run in linear time. — merlin2011, Dec 31 '16 at 22:44

score 6 · Accepted Answer · answered Dec 31 '16 at 22:25

If you don't mind changing the structure of your algorithm a bit more, you can calculate the values in a bottom-up fashion, starting with the smallest values.

def specialMultiplication(max_n):
    a = b = 1
    for n in range(1, max_n+1):
        a, b = b, a*b*n
    return b

score 4 · Answer 2 · edited May 23 '17 at 11:45

4

Convert the recursion to an iterative function using an auxiliary "todo list":

def specialMultiplication(n):
    to_process = []
    result = 1
    if n >= 2:
        to_process.append(n)
        while to_process:  # while list is not empty
            n = to_process.pop()
            result *= n
            if n >= 3:
                to_process.append(n-1)
                if n >= 4:
                   to_process.append(n-2)
    return result

create a work list (to_process)
if n >= 2, add n to the list
while to_process is not empty, pop item from list, multiply to result
if n-1 < 2, don't perform "left" operation (don't append to work list)
if n-2 < 2, don't perform "right" operation (don't append to work list)

This method has the advantage of consuming less stack. I've checked the results against recursive version for values from 1 to 25 and they were equal.

Note that it's still slow, since complexity is O(2^n) so it's beginning to be really slow from n=30 (time doubles when n increases by 1). n=28 is computed in 12 seconds on my laptop.

I've successfully used this method to fix a stack overflow problem when performing a flood fill algorithm: Fatal Python error: Cannot recover from stack overflow. During Flood Fill but here Blcknght answer is more adapted because it rethinks the way of computing it from the start.

edited May 23 '17 at 11:45

Community

1
1

answered Dec 31 '16 at 22:16

Jean-François Fabre

137,073
23
153
219

I just tried that, and it worked for small numbers. But it still takes an decent amount of time when you reach, say, 90. Is there any way to speed that performance up? – firelover Dec 31 '16 at 22:24
I see that it'd still be slow, now. What would be a good way to translate this to a dynamic style? I'm not versed at that, sadly (but at least it points out something to learn!) – firelover Dec 31 '16 at 22:37
Even if it's not the translation of your function to iterative, BlckKnght answer is much faster. – Jean-François Fabre Dec 31 '16 at 22:39
I see that now. I wish I could give you both the correct answer, since yours was iterative, which is what I asked for, even if his is faster. – firelover Dec 31 '16 at 22:52
His answer is also iterative. Dont you worry, I got 4 upvotes out of it and it was fun to code so I m good. – Jean-François Fabre Dec 31 '16 at 23:01

score 2 · Answer 3 · answered Dec 31 '16 at 23:20

The OP's function has the same recursive structure as the Fibonacci and Lucas functions, just with different values for f0, f1, and g:

f(0) = f0
f(1) = f1
f(n) = g(f(n-2), f(n-1), n)

This is an example of a recurrence relation. Here is an iterative version of the general solution that calculates f(n) in n steps. It corresponds to a bottom-up tail recursion.

def f(n):
    if not isinstance(n, int):  # Can be loosened a bit
        raise TypeError('Input must be an int')  # Can be more informative
    if n < 0:
        raise ValueError('Input must be non-negative')
    if n == 0: 
        return f0
    i, fi_1, fi = 1, f0, f1  # invariant: fi_1, fi = f(i-1), f(i)
    while i < n:
        i += 1
        fi_1, fi = fi, g(fi_1, fi, n)  # restore invariant for new i
    return fi

Blckknight's answer is a simplified version of this

Converting a function with two recursive calls into an interative function

3 Answers3