Recursion for Dummies

Recursion is a fundamental construct in computation. You should not freak out by seeing it.

Some problems are hard. It is challenging to form a mental model for those. Nevertheless, we have a powerful tool at our disposal. Recursion! It is a robust idea.

Say you were solving a problem. You got something in your mind. It is something iterative but fuzzy — not so clear. Still, you feel that could be the solution. However, you can’t implement it. Well, there is a pretty good margin that the solution would be recursive.

This piece is intended for beginners who learned some looping and function kind of stuff here and there. It would be better if you have already been introduced to the idea, recursion, but you did not find it too intuitive.

I will be using python here, because, well, pretty much everyone does that. What I want you to do is run each piece of code as you see it. I would prefer that you type it all instead of copy-pasting.

After going through this article you would gain

1. Understanding on what is recursion
2. Practice by solving four recursive problems
3. Elegance vs Performance
4. Why do you need to write recursive functions

What the heck recursion even means?

Informally, a recursive function is something that has a base case and a recursive call that means calling the function itself. That's it. No more no less.

Problem 1

Write a function, power, that takes a number num and a positive integer pow— it returns the value of raising num to the power of pow.

To illustrate,

1. power(2, 3) would return 8
2. power(5, 5) would return 3125

To discover the base case let us first understand what it formally means to raise num to the power pow.

It is,

num * num * num * num (pow times) . For instance, 5 ^ 3 = 5 * 5 * 5 = 125

But there is a catch. Any number when raised to the power 0 would equate to 1. Perfect! This could be a pretty solid base case. In the code, we would be saying that when the function is called with a pow value of 0 we would be returning 1.

All it says is whenever the p is 0 return 1

Now, we have to define the function in terms of the same function.

5 ^ 3 = 5 * 5 ^ 2 or pow(5, 3) = 5 * pow(5, 2) .

In general, n ^ p = n * n ^ (p-1) .

As we have done defining the function in terms of itself we can now code it up.

Now, write it yourself. Run it. Try to understand it before moving to the next problem. Alternatively, you may try this nice visualization tool.

Problem 2

Define a function that would take a positive integer num and return the factorial of it.

If you have never heard of factorial before check out this awesome primer to factorial.

Factorial of a positive integer N is defined as follows,

N! = N * (N-1) * (N-2) * … * 2 * 1

So, to make the recursive call, we need to define the function in terms of itself. In the case of factorial, it would be pretty easy as N! = N * (N-1)! . Again, if you don’t get this please check the guide on factorial linked above.

Can you think of the base case? It comes straight out of the definition as the factorial of zero is defined as one. ( 0! = 1 )

It would be impressive if you try to write the code on your own using the information and the example of the first problem.

Step 1: Coding up the base case

Step 2: Making the recursive call

Pythontutor visualization

If you have made it this far congratulations! Now, you are a bit more confident writing recursive functions. Let’s try to write some more recursive functions to solidify your understanding.

A more structured mental framework

As I have told before recursion is actually a mathematical construct. Therefore, it has some formal definition and proof kind of stuff. To save your nice little brain from getting baffled you may follow the following steps whenever you are solving a recursive problem.

Step 1: The base case

The base case is the most crucial part of a recursive function. It needs to be rock solid. If there was any leak in that — meaning if your recursive call never hits the base case — you have risked your code to throw an exception widely known as the StackOverflow exception. Under the hood, your program makes infinite recursive calls, and thus a stack gets created for each call. The stack memory is limited. Hence the base case is the key for a recursive function.

Step 2: The recursive call

The recursive call is difficult to get right. Running a recursive call back on your mind would be painful.

However, you could simply do this instead,

1. Assume the function works for all the other inputs. That means you have to assume your recursive call works.
2. Now, make the function work for the current input

This is actually the way through which recursive proof works. It is called proof by induction. However, it is not necessary to learn it to solve problems recursively.

Problem 3

Define a function that would take a positive integer num and return a list containing the elements from this range [N,1] .

For instance,

1. makeList(5) would return [5, 4, 3, 2, 1]
2. makeList(1) would return [1]

Can you see the base case here? It is the second example. Whenever our function is called with an argument of 1 it would simply return a list containing that argument i.e [1] .

The base case is solid. No matter what valid input the function is thrown, if the recursive call is constructed accurately, it would inevitably resort to the base case thus avoiding the StackOverflow exception.

For the recursive call, we would take a slightly different approach. First, we would store the result of the recursive call in a variable.

As per the recursive mental framework I have stated above at this point we are done with the base-case and the recursive-call . We would assume the recursive call does its job as we have assumed that the function works for all other inputs.

Now, we have to only make it work for the current input.

We are done.

Problem 4

It would be the last problem we will be seeing for today. It’s similar to the last one. So, you, if haven’t already, may try to get your hands dirty on this one.

Define a function that would take a list of integerslst and the length l as parameters and would return the sum of all the elements of the list.

To illustrate,

1. sumList([1, 2, 3, 4, 5], 5) would return 15
2. sumList([9], 1) would return 9

The base case is straightforward as I have already shown that to you in the example cases. Whenever the length of the list is 1 the function would simply return the first element, effectively the only element, of the list.

Let’s think about the recursive call. Think it this way, the sum of all the elements of an integer list of length N would equate to the first element of the list added with the sum of the rest of the elements of the list. That is the key to framing the recursive call. Defining the function in terms of the same function.

Elegance vs Performance

Once you get familiar with writing recursive functions you would really appreciate how elegant the recursive implementation can be as compared to the iterative implementation. If you follow the said mental framework recursive code would be so easy to read.

However, recursive functions are not as performant as iterative ones. As it involves creating a stack-frame for each recursive call. Although, there is an idiomatic way of writing tail-recursive functions. Tail-recursion is not common in the imperative paradigm but has first-class support in functional languages. A tail-recursive function can get the job done with only one stack and thus becoming equally performant with the iterative one.

Do you need to write recursive functions?

One obvious question that may come to your mind is whether you need to write recursive functions at all. Since all the code that I have shown so far can easily be implemented with a simple for loop. Well, actually all these examples operated with either sequential math functions or linear data structures. It is true that in these particular use cases an iterative implementation would be fine.

However, let me remind you that these were really basic instances of recursive functions to orient you with the concept. You would only realize the true power of recursion when operating with tree-like data structures. Tree-like data structures are fundamentally designed to be recursive.

I appreciated recursion for the first time when I stumbled upon the classic Towers of Hanoi problem. I would urge you to check the following video out. It is a mesmerizing manifestation of a simple-looking but insanely difficult problem. After learning about the solution make sure to think about the iterative implementation. I can’t even imagine how ugly it would be.

Summary

Here is the summary of the whole piece,

1. Recursion is powerful
2. Any iterative construct can be implemented recursively
3. A recursive function needs a solid base case. Otherwise, you may run into the StackOverflow exception.
4. For the recursive call, you have to define the function in terms of the same function.
5. When writing the recursive call, assume that the function works for all other inputs. Then make it work for the current input.
6. Arguably, recursion is more elegant as compared to iteration.
7. Recursion can be less performant as compared to iteration because it involves creating a new stack for each operation.
8. The performance issue can be avoided by writing an idiomatic construct known as tail-recursion. It has widespread support in the functional paradigm.
9. For sequential math functions and linear data structures iterative implementations are usually readable and simple.
10. For tree-like data structures recursion is more suitable as these data structures are fundamentally recursive.
11. To appreciate recursion, for the first time, you may check out the Towers of Hanoi problem.

I am glad that you have made it thus far. Hopefully, now you are a bit more familiar with recursive-constructs that you may have avoided for so long. Enjoy your journey with recursion.

I would really appreciate a couple of words on your thought.✏️

You can support my work by buying me a cup of coffee. ☕

Nilanjan 🌱🌱 is writing programming-related articles