Recursion (again)

Well, I already wrote some stuff down about recursion, but I will add more this week since we have been instructed to do so. Some of my classmates dislike recursion because they find it kind of frustrating. Well they are right to think that way since it is harder to understand or implement a recursive function rather than a non-recursive one. But that is not a good excuse, because sometimes recursive algorithms can be way easier to understand. It might be hard to get used to it but recursion is actually really useful. It makes some kinds of tasks much easier to implement, and makes the code much simpler. And in some cases there is no other way to implement the task(or at least I can't think of any...).  You should to use it when there is a pattern repeated multiple times with small differences between each step. I want to show an example why recursion is sometimes indeed the easier way to do things even though it sometimes looks so complicated.

An example of a situation where it is much more intuitive to use a recursive algorithm would be when implementing a program to calculate the n-th Fibonacci number. For those who never heard about it before, the Fibonacci numbers are a sequence of integers where each number is the sum of the two preceding numbers from the sequence. So the sequence goes on like this 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...
I quickly implemented a program to calculate the nth fibonacci number:

 def fib(n):  
   if n <= 1:  
     return n  
   else:  
     return fib(n-2) + fib(n-1)  
     

But if I had insisted on not using recursion, the code would have been much more complicated, while not having any advantage over the recursive code:

 def fib(n):  
   if (n <= 1):  
     return n  
     
   current = 1  
   previous = 1  
     
   for i in range(2, n + 1):  
     temp = current  
     current += previous  
     previous = temp  
     
   return temp  

As you can see, the recursive example is much easier to understand(and much cleaner) in this case.