title: Why does backward recursion execute faster than forward recursion in python
body: <p>I made an algorithm in Python for counting the number of ways of getting an amount of money with different coin denominations:</p>
  
  <pre><code>@measure
  def countChange(n, coin_list):
      maxIndex = len(coin_list)
      def count(n, current_index):        
          if n&gt;0 and maxIndex&gt;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)
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>@measure
  def countChange2(n, coin_list):
      maxIndex = len(coin_list)
      def count(n, current_index):        
          if n&gt;0 and 0&lt;=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)
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>print(countChange(30, range(1, 31)))
  print(countChange2(30, range(1, 31)))
  
  &gt;&gt; Call to countChange took 0.9956174254208345 secods.
  &gt;&gt; Call to countChange2 took 0.037631815734429974 secods.
  </code></pre>
  
  <p>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?</p>