Dungeon Coder

 

Dungeon Within a Dungeon Within a Dungeon

Introduction to Recursion

Gird your loins, because the dungeon is about to get treacherous. Recursion sounds scary. It even looks a little scary at first. I promise, however, that recursion can actually make your coding life easier.

What is recursion? For the puroses of programming, we will speak of recursion in terms of recursive functions. So, recursion for us will refer to a way of writing functions. A recursive function is one which is designed to call itself. What does that even mean?

The first example most often used to demonstrate recursion is to write a function that recursively solves exponentiation. In case you don't remember, exponentiation is when we raise some base to the power of some exponent. You know, like 2 cubed is 2 to the 3rd power, 3 squared is 3 to the 2nd power, and so on. The reason that this is often the first example has to do with the recursive nature of solving exponentiation.

What is involved in raising some base to some exponent? Well, let's take 2 cubed as an example. To raise 2 to the 3rd power is to take three twos and multiply them together. 2 x 2 x 2 = 8. A bit of an anal nitpick: people often incorrectly say that 2 cubed is when you take 2 and multiply it by itself 3 times. Nope. Wrong. 2 cubed is actually 2 times itself 3-1 times. 2x2x2. Right? I mean 2x2 is the same as saying 2 times itself once. 2x2x2 is the same as saying 2 times itself twice. So, 2 times itself 3 times would be 2x2x2x2, which is not 2 cubed.

Okay, enough with the rant. How is this recursive? Well, let's look at the problem recursively. If 2 cubed is 2x2x2, then we can also say that 2 cubed is the same as 2x2squared. Even deeper, we can say that 2 squared is the same as 2 x 2 to the first power. In short, we can break down 2 to the cubed into much smaller, simpler problems until we get to the easiest possible case.

That brings us to two important concepts in recursion: the base (or basis) case and the general (or recursive) case. The base case means a case that shouldn't be broken down any further. The recursive case is one that needs to be broken down into a smaller version of itself. So, 2 cubed is a recursive case - it can be broken down. Is 2 squared a base case? Nope, still a recursive case since it can be broken down even further. How do we know, then, when we've reached a base case? Well, that's actually up to us to decide to some extent. In the case of exponentiation, we have a few potential base cases, and we can use all of them if we want.

One base case in exponentiation is when the base is 0. Remember, 0 times anything is always 0. Another base case is when the base is 1. Rember that 1 times itself will always be 1. So 1 squared, 1 cubed, and so on will all be 1. Yet another base case is when the exponent is 0. In that case, the result will always be 1. Anything to the 0th power is 1. Finally, our last base case is when the exponent is 1. In that case, the answer will be the base. Anything to the 1st power is always itself.

Enough babble. Let's play.

Take your time reading through that code and analyzing the function calls and resulting output. Consider the if statements and the recursive calls. That is, take a look at how the recursiveExp function is called within its own definition. That is recursion. We'll dive a bit deeper into recursion as we progress through further episodes. For now, consider the following assignment.

Assignment:

  1. Add another print line that calls the recursiveExp function and pass it a negative value as the base argument. What happens?
  2. Add a line that prompts the user to enter in a base, and store that number in a variable called userBase. Add another line that asks the user to enter an exponent and store that number in a variable called userExp. Call the recursiveExp function using your two variables as the arguments.
  3. Add a for loop that repeats question 2 3 times. However, unlike in question 2, this loop should take the base and exponent and add them as key:value pairs to a dictionary. You first have to create the dictionary yourself and name it whatever you want.
  4. Now, use a for loop to iterate through your dictionary, each time through calling the recursiveExp function to raise the key to the power of the value and printing the result to standard output.
  5. I think questions 3 and 4 were enough. Take a breather.

Join the Dungeon Crawl: A place for programmers to ponder, partake, and peruse postulations pertaining to programming, politics, potions, and pizza.

If you subscribe on Patreon, you will be granted access to the Dojo, a growing collection of quality computer science classes created and actively mantained and frequented by the Dungeon Master!

Become a Patron!

Glossary

Contact: dungeon_master@dungeoncoder.com