3

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!

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

3 Answers 3

Reset to default
6

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
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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
  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.

Improve this answer

5 Comments

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?
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!)
Even if it's not the translation of your function to iterative, BlckKnght answer is much faster.
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.
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.
2

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

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.