title: Any way to make recursive functions faster?
body: <p>After some research about recursive functions i am facing contradiction: On one side solving problems in recursive way is elegant while on the other side in practice performance seems to be horrible and number of recursive calls is limited.</p>
  
  <p>I understand by default Pythons recursive depth is limited to 1000, however even in a simple application i get very bad performmance as early as 40 - 50 calls.</p>
  
  <p>Let me give an example:</p>
  
  <pre><code>def fibonacci(n):
      if n == 1 or n == 0:
          return 1
      else:
          return fibonacci(n-1) + fibonacci(n-2)
  </code></pre>
  
  <p>This simple recursive function on my PC takes huge amount of time to solve even for low n. For testing i also wrote another function:</p>
  
  <pre><code>def fib_nonrecursive(n):
      fib_seq = [1, 1]
      for i in range(2, n+1):
          value = fib_seq[i-1] + fib_seq[i-2]
          fib_seq.append(value)        
      return fib_seq[i]
  </code></pre>
  
  <p>Non recursive way is very fast even on big numbers, so definitivly problem cannot be operations involved or size of numbers. So my question is why the recursive way is so slow and is there any way to make it faster? Is there any way to expand resursive depth?</p>
  
  <p><strong>EDIT</strong> 
  Since answers suggested using memoization i looked into it and implemented it on my example:</p>
  
  <pre><code>def mem(f):
      memory = {}
      def inner_function(x):
          if x not in memory:            
              memory[x] = f(x)
              return memory[x]
          else:
              return memory[x]
      return inner_function
  
  @mem
  def fibonacci(n):
      if n == 1 or n == 0:
          return 1
      else:
          return fibonacci(n-1) + fibonacci(n-2)
  </code></pre>
  
  <p>Same <code>mem(f)</code> can be used with other recursive functions <code>f</code>. The <code>@mem</code> part must be included for <code>f</code> to be passed as argument to <code>mem()</code> (see "decorators")
  It is slightly advanced way to code but i didnt find an easier was to implement memoization for given example. If there is simpler way of implementation pls correct me.</p>