Recursion: functions that call themselves

Part 1: Factorial example

When I first started doing coding exercises and challenges, I had troubles, like we all did in the beginning. But even if I couldn’t figure out how to solve something, looking at the final solution always helped. After all, lines of code follow a logical pattern that if you think about, isn’t too hard to understand. That was until I first faced recursion. A function is calling itself (!!!), what the actual hell?! How is that even possible?

That is when I have decided that figuring it out is something I need to do as soon as possible. Recursion challenges are not only given on technical interviews, they are widely used and allow to break complex tasks into smaller subproblems. Understanding the code and math of recursion is very important. To all of us.

There are many examples of recursion exercises. Some of them are truly mind-blowing and incredibly elegant — such as Towers of Hanoi, some are art-related (hello Fibonacci sequence), but in this case I would like to talk about the most fundamental recursion example — factorial.

From school we remember that to calculate factorial we need to take the product of a given number and all the preceding integers. Let’s look at the actual formula for x!:

Wait a minute. Why in the world would we even need to calculate something like this? Okay, we need addition to figure out how many apples you and your friend have combined, we need multiplication to figure out the area of a football field, we need exponents in case if the field is square, but why do we need factorials?

Factorials represent the number of ways we can arrange objects on a line.

How can we arrange one apple on a line? Only one way to do it. What about two apples, one green, one red? Red first, green second or green first, red second — two ways. Three apples, red, green, yellow:

1. red, green, yellow
2. red, yellow, green
3. yellow, green, red
4. yellow, red, green
5. green, yellow, red
6. green, red, yellow

Six ways. Think about separate events happening in time is a specific order, and we’re getting closer to probability, which is much more useful than just arranging apples. So, we need factorials. How do we calculate them, fast?

def factorial(x):
 if x == 1:
  return 1
 else:
  return x*factorial(x-1)

Again, a function is calling itself, what a miracle! But this logic comes from the very definition of recursion: Recursion is the process of defining something in terms of itself.

Let’s try to follow what happens on each step. Easiest case: we give it 1. In the very beginning of the if-statement the function will check if the given number is equal to one. And in this case it is, so the rest of the code will never get executed and the factorial(1) will return one. Next, we try to give it two. This time the first bit of the if-statement will not get executed at first, it will read the else condition. If the given x is not equal to 1, than I need to take this number and multiply it by some unknown function ‘factorial’ of (x-1). What’s the given x again? 2. What’s the (x-1)? 1. Do I know what a factorial(1) is? Let’s go back to the top. If the number is one, then I need to return 1. Great, now we can just multiply our given x, which is 2, by the factorial of 1, which is 1, so I need to return 2*1=2.

Basically, this logic is executed over and over again until it hits the first bit of the if-statement — until the number is equal to one.

0!

We heard that 0! is equal to 1. Let’s plug it into our function above:

factorial(0)

And get the error:

Turns out, our function doesn’t handle the case when we plug in 0. But the math.factorial(0) calculates it with no problems. What’s wrong? Should we just add an elif condition?

We could, but it would be cheating and cutting corners. Let’s look again at the mathematical formula of the factorial and try to rearrange it a little. Curious fact: without messing with the definition of recursion or factorial, we can express x! not just in terms of preceding numbers, but in terms of a following number, (x+1):

Here is how we would calculate it for several numbers and reach zero:

So finally, we can update our factorial(x) function:

def true_factorial(x):
 
 def factorial(x):
  if x == 1:
   return 1
  else:
   return x*factorial(x-1)
 
 return int(factorial(x+1)/(x+1))

I hope my way of understanding basic recursion helps. I will post more about it next week!

Resources:

Numberphile

Programiz