Week #7: Recursion

"Recursion is truly one of the most beautiful and elegant tools in computer science." 

Perfect example of recursion in
everyday life

I couldn't agree with the above statement any more. I spoke about recursion briefly in my Week #4 post but since that time, I have grown to learn and understand recursion more than ever. What is recursion? Recursion is a method of solving problems which have similar problems lodged within them. It is used (in python) by creating a function which calls itself repeatedly until the problem within the problem is solved and then that answer is used to solve a bigger problem. This is very helpful in solving complex algorithms. It's difficult to understand but once you start using it, you tend to get the hang of it.  

Before when computer hardware was still at its early stages, recursion cost a lot of money. But now, due to the advancement in hardware technology, recursive is cos efficient and saves time from working out and maintaining the algorithm by hand. Also, it is free from error (if the code is written well enough).

There are three main things that need to be known in building a recursive function. 

1. The recursive function must have a base case. - The reason for this is that the function must terminate somewhere. If there is no base case the recursive function will keep going and will throw out an error at you. 
2. A recursive function must change itself and work towards its base case. - This is quite obvious because if the function were to call itself using the same arguments, the function would just end in an infinite loop which, once again, will throw an error at you.
3. The most obvious one is that the recursive must call itself, recursively. Without this, there is no recursive function.

Let's take an example of a simple function to use which will need recursion to work. Let's say we have a list of lists and we want to add all the numbers within them.

List = [0,1,2,[0,1,3],1]

First thing we would need to determine is the base case. So we know that we want to go through each item. For that we would use a for loop. Now we know that if the item we are getting is a number, we want to add that. But if it's a list, we need to go through that and add the numbers within them. So it would look something like this:

def add_num(num_list):

              total = 0

              for item in num_list:

                          if isinstance(item, list):                    #This will tell us if we need to go 
                                                                                     #through the function again. If we  
                                                                                     #do, we will need to store it 
                                      temp = add_num(item)      #somewhere and add that to the
                                      total += temp                     #total.                                        

                          else:

                                 total += item                            # This will count as the base case

              return total

So that's basically recursion. If you follow the above steps, you'll usually end up with a correct function. Until next time.