Why does backward recursion execute faster than forward recursion in python

Question

I made an algorithm in Python for counting the number of ways of getting an amount of money with different coin denominations:

@measure
def countChange(n, coin_list):
    maxIndex = len(coin_list)
    def count(n, current_index):        
        if n>0 and maxIndex>current_index:
            c = 0
            current = coin_list[current_index]
            max_coeff = int(n/current)      
            for coeff in range(max_coeff+1):
                c+=count(n-coeff*current, current_index+1)
        elif n==0: return 1
        else: return 0
        return c
    return count(n, 0)

My algorithm uses an index to get a coin denomination and, as you can see, my index is increasing in each stack frame I get in. I realized that the algorithm could be written in this way also:

@measure
def countChange2(n, coin_list):
    maxIndex = len(coin_list)
    def count(n, current_index):        
        if n>0 and 0<=current_index:
            c = 0
            current = coin_list[current_index]
            max_coeff = int(n/current)      
            for coeff in range(max_coeff+1):
                c+=count(n-coeff*current, current_index-1)
        elif n==0: return 1
        else: return 0
        return c
    return count(n, maxIndex-1)

This time, the index is decreasing each stack frame I get in. I compared the execution time of the functions and I got a very noteworthy difference:

print(countChange(30, range(1, 31)))
print(countChange2(30, range(1, 31)))

>> Call to countChange took 0.9956174254208345 secods.
>> Call to countChange2 took 0.037631815734429974 secods.

Why is there a great difference in the execution times of the algorithms if I'm not even caching the results? Why does the increasing order of the index affect this execution time?

yes ... this is how dynamic programming works (this is an example of dynamic programming, you start at the goal state, and work backwards allowing you to skip calculations that would result in an invalid solution)... however if you start at the initial state it takes an exaustive search and does not know an answer is invalid until after calculating it — Joran Beasley
– Joran Beasley, Commented May 7, 2014 at 18:41
The number of calls is dependent on the order of input. You can get the minimum number by sorting the list in descending order in countChange. coin_list.sort(reverse = True) — Sean Fujiwara
– Sean Fujiwara, Commented May 7, 2014 at 19:24
@JoranBeasley: Starting at the "goal state" and working back to the "start state" doesn't automatically make an algorithm "dynamic". Suppose I have a maze with exactly two doors, A and B. You're telling me that if I label A "enter" and B "exit", and you start at B, then you are doing some kind of "dynamic programming" maze solving? What if I switch the labels so that A reads "exit" and B reads "enter". Have I suddenly made your maze solver not dynamic anymore? — John Y
– John Y, Commented May 7, 2014 at 20:13

Adam · Accepted Answer · 2014-05-13 04:32:13Z

12

This doesn't really have anything to do with dynamic programming, as I understand it. Just reversing the indices shouldn't make something "dynamic".

What's happening is that the algorithm is input sensitive. Try feeding the input in reversed order. For example,

print(countChange(30, list(reversed(range(1, 31)))))
print(countChange2(30, list(reversed(range(1, 31)))))

Just as some sorting algorithms are extremely fast with already sorted data and very slow with reversed data, you've got that kind of algorithm here.

In the case where the input is increasing, countChange needs a lot more iterations to arrive at its final answer, and thus seems a lot slower. However, when the input is decreasing, the performance characteristics are reversed.

edited May 13, 2014 at 4:32

Adam

15.8k2 gold badges46 silver badges64 bronze badges

answered May 7, 2014 at 19:15

John Y

14.6k2 gold badges51 silver badges76 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Joran Beasley Over a year ago

it does though(make it a dynamic programming solution) with this problem specifically, since reversing it allows you to not even explore invalid path. it also ensures that you only calculate each subproblem once ... (+1 all the same, since yes the reason it is slower is it calls more times ...)

John Y Over a year ago

@JoranBeasley: I think you really have misunderstood dynamic programming. Either that or you didn't take the time to examine the properties of this problem. See my edit.

Joran Beasley Over a year ago

your right .... im still not sure... I thought I understood dynamic programming, now im doubting myself (also I didnt really examine the algorithm OP was using... it looks like lots of stuff is recalculated ... all over the place, regardless of order) ...

Joran Beasley · Accepted Answer · 2014-05-07 21:14:58Z

8

thre number combinations are not huge

the reason is that going forward you have to explore every possibility, however when you go backwards you can eliminate large chunks of invalid solutions without having to actually calculate them

going forward you call count 500k times

going backwards your code only makes 30k calls to count ...

you can make both of these faster by memoizing the calls , (or changing your algorithm to not make duplicate calls)

edited May 7, 2014 at 21:14

answered May 7, 2014 at 18:40

Joran Beasley

114k13 gold badges167 silver badges187 bronze badges

10 Comments

rfrm Over a year ago

Dynamic programming needs of a mean of saving previous results, as you can see, I'm NOT saving nothing.

Joran Beasley Over a year ago

no it doesnt it typically is recursively called(although nothing forces that its just the most intuitive way) ... just like you are doing ... this is dynamic programing and this is also why starting in start state is much slower than starting in your goal state ... (in fact the tutorial I wrote is this exact same problem statement)

rfrm Over a year ago

"Reversing it allows you to not even explore invalid path" @Joran this makes sense, Thank you.

Joran Beasley Over a year ago

I figured bolding parts of my answer would help :P people were getting too hung up on semantics :P (me too ... maybe Im wrong and this isnt actually dynamic programming... but Im pretty sure :P)

user2357112 Over a year ago

This is not dynamic programming. Dynamic programming is fundamentally about dividing a problem into overlapping subproblems and reusing the results of subproblem computations. Nothing is reused here; in fact, count is called repeatedly with the same arguments in both versions. John Y's answer is significantly more accurate.

|

Collectives™ on Stack Overflow

Why does backward recursion execute faster than forward recursion in python

2 Answers 2

3 Comments

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related