week 7 recursion

The midterm storm has finally passed, and I now have sometime to write something about recursion in python programming at last. Recursion , which is a way of coding that a function can call itself  one or more times, is said to be the most magic and important concept in python. From my perspective, recursion  is a method that solves a problem by working on smaller instances of the same problem. It is an easy and elegant way of coding in my eyes, since a problem can be solved by using only a few or even one line of code, which is really amazing and attractive to me, since I am always  too lazy to write loops. However,  according to a friend of mine who studies ECE, recursion may not be as efficient as loop in some cases, which made me pretty curious and I did some google research. According to my research, what my friend said is true. From the website I read, they use an example of Fibonacci sequence. The recursive method they write would be as follows:

Def fib(n):

       If n==0:

             Return 0

       elif n==1:

             Return 1

       else:

             Return fib(n-1)+fib(n-2)

Also, they give an iterative way as below:

Def fibi(n):

       a,b = 0, 1

       for i in range (n):

             a,b =b, a+b

       Return a 

After that they write a script where use the timeit module to measure the speed of both ways of calls. The results is pretty surprising as fibi(40) is 13millions times faster than fib(40), and that's due to no menmory of previously calculated values for resursion according their analysis by using tree structure. But this pitfall can be solved by using a dictionary to save previously calculated values. The website I browsed is www.python-course.eu/python3_recursive_functions.php, where you can find the code and analysis results above. Also if you are interested you can check the website for their timeit data and tree structure analysis, which also does a little help for our tree knowledge.