CODEWITHSUNDEEP
pythonpython-3.xrecursion
firelover
firelover

Reputation: 41

Converting a function with two recursive calls into an interative function

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!

Upvotes: 3

Views: 425

Answers (3)

Terry Jan Reedy
Terry Jan Reedy

Reputation: 19144

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

Upvotes: 2

Jean-Fran&#231;ois Fabre
Jean-Fran&#231;ois Fabre

Reputation: 140168

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
  1. create a work list (to_process)
  2. if n >= 2, add n to the list
  3. while to_process is not empty, pop item from list, multiply to result
  4. if n-1 < 2, don't perform "left" operation (don't append to work list)
  5. 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.

Upvotes: 4

Blckknght
Blckknght

Reputation: 104712

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

Upvotes: 6

Related Questions