Recursion: The Basics

Recursion. Possibly a Computer Scientist's favorite topic. It's a very deep topic and you could easily write a masters or Ph.D. thesis on some of the more complicated recursive

algorithms. This post will stay pretty basic.

Recursion is the idea of a method of function that calls itself and passes in a slightly different value. A classic problem is the Fibonacci sequence. The Fibonacci sequence is defined mathematically as

So your first number is always 0. Your second number is always 1, and then the next number is the sum of the previous two. So the sequence goes like this

0, 1, 1, 2, 3, 5, 8, 13.....

And so on forever. If you need a better explanation of the Fibonacci sequence, let me know and I can write one up.

So let's say your grade school teacher is mean and asks you to find the 50th Fibonacci number (and she takes away your smart phone so you can't google it). This is basically a lot of busy work, write? And who has the energy in their hand to write out 60 numbers. Number crunching and busy work are what computers are good at, so let's take a look at a Fibonacci sequence solving program

It's honestly that simple. The first thing we do is check if we already know the number. If we are looking for the zeroth or first fibonacci number, we know the answer. If we don't, we have to recurse and find it. No matter how big your number, your program will keep subtracting one and two from that number until it is dealing with something it knows.

Why should you care?

This is a complex topic, but I fully believe that part of being a good computer programmer is to get interested in these more complex topic. If you find yourself looking at my example and wondering about the details, or realize you are typing it up yourself to make sure I didn't make a mistake, you should strongly consider making this your major. You're probably getting hooked on a fascinating field.