Week 7 - Recursion

Hey guys!

So this week’s assigned topic is Recursion! I still haven’t perfected actually writing code recursively, but I’m going to do my best to give a general overview on what it is and how it works.

What is Recursion?

So recursion is writing a function in terms of itself. In other words, it’s like the inception of code, you’re writing a function that can call itself. This picture basically sums it up:

So the reason people use recursion is because it’s easier to solve problems by writing recursive functions. It allows you to use a function to solve the big picture, and then call the same function to solve smaller sub problems.

How does recursion work?

Recursive functions are similar to if/else statement. For example:

def r_sum(nested_num_list):

                tot = 0

                for element in nested_num_list:

                                if type(element) == type([]):

                                                tot += r_sum(element)

                                else:

                                                tot += element

                return tot

The key part of this recursive function, or any recursive function for that matter, is the base case, which is highlighted. This is the part of the function where it doesn’t actually call itself. Without the base case, the function would go into an infinite loop (infinite recursion) and you’d never get an answer, which isn’t what we want.

If we entered sum([2, [3, 4] 5]) into the python shell, this is what would happen: 

1. Since the first element is an int, not a list, it will go straight to the base case (else) and 2 will become the new total
2. Since 3 is in a separate list, the function would go to the “if” and call the function again, so that the contents of the list can be added.
3.  Since the function is called again, a new total would be created and 3 and 4 would be added to make.This total is then added to the original total to make 9, and the function continues to the last number which is 5.
4. The output of this would be 14.

When is recursion used?

Recursion is used a lot when creating functions and methods for trees, since they are all so similar. It makes it easier to write tree functions recursively to search through nodes and leaves in a tree to find a particular value or to check if all numbers are the same type. Basically recursion is used a lot to traverse trees.

For example, one recursive tree function is:

def total(tree):

                if tree is None: return 0

                return total(tree.left) + total(tree.right) + total.cargo

This recursive function finds the total value of the cargo of the given tree, and all its children.

How have I found learning about recursion?

Well since this was a completely new concept, I found it confusing at first and pretty hard to understand. I still haven’t mastered it but I’ve definitely got a better understanding of it and can write my own recursive functions more easily. I found that once you understood what you needed as your base case, it was a lot easier to write functions recursively, since you’re just putting in place where you want your function to loop! It was definitely an interesting learning process and I now find recursion pretty useful, especially when you want to solve a big problem that has smaller and similar sub-problems.

Mini Glossary

Recursion: Writing a function in terms of itself.

Recursive call:  When you call a function in its definition.

Base case: The part of the function where there is no recursive call.

Infinite recursion: When the function goes into an infinite loop since there is no base case.