Recursion is everywhere!

iIn this blog I’m going to explain you one of the most complex concept in programming, RECURSION. So much software engineers run away from this concept. I have to admit that it is hard to understand at the beginning, but if we try more and more we can get it. I will try to help you understand this using examples and some illustrations.

Believe it or not, recursion is everywhere. Nature provides numerous examples where we can observe this property. For instance, a branch of a tree can be understood as a stem, plus a set of smaller branches that emanate from it, which in turn contain other smaller branches, and so on. Recursion also appears in art. A well-known example is the Droste effect, which consists of a picture appearing within itself. In theory the process could be repeated indefinitely, but naturally stops in practice when the smallest picture to be drawn is sufficiently small (for example, if it occupies a single pixel in a digital image).

While the recursive entities in the previous examples were clearly tangible, recursion also appears in a wide variety of abstract concepts. In this regard, recursion can be understood as the process of defining concepts by using the definition itself. Oh!, you are thinking: ”WHAT?, say it slowly again”. Well it’s more simple thinking in this concept like this:

It’s the idea of taking a problem and reducing it to smaller versions of the same problem.

So, in the context of computer programming, recursion should be understood as a powerful problem-solving strategy that allows us to design simple and elegant algorithms for solving computational problems. They are instructions that repeats again and again until finally find a condition that ends the repetition call (find the smallest version of the problem to solve). If you are thinking is the same as a loop, yeah it is!. But this is more elegant and interesting way to solve the problem. So, every loop can be sustitute by recursion. So, why would I do this recursively if I can do it easily with a loop? you may be thinking. Well, this is a sneak peek into functional programming! Functional programming languages like Haskell don’t have loops. If you have a good understanding of recursion, functional languages will be easier to learn.

What is the Stack and why is it important?

As can be seen in the image below, the name “stack” comes from the analogy of stacking physical items on top of each other. While putting items on and taking them off is easy, getting items deeper in the stack require taking multiple other items off first. A stack is either empty or it consists of a “top” and the rest, which is the stack.

Data structure illustration (www.freecodecamp.org)

So, your computer uses a stack internally called the call stack. It is a mechanism for an interpreter to keep track of its place in a script that calls multiple functions, what function is currently being run and what functions are called from within that function, etc.

• When a script calls a function, the interpreter adds it to the call stack and then starts carrying out the function.
• Any functions that are called by that function are added to the call stack further up, and run where their calls are reached.
• When the current function is finished, the interpreter takes it off the stack and resumes execution where it left off in the last code listing.

The importance of knowing this concepts is that we will help us to understand how recursion works.

Recursion is easier if we know the call stack process.

Base case and recursive case

It’s important understand another concepts inside recursion. When you write a recursive function, you have to tell it when to stop recursing if you don’t want a infinite loop. That’s why every recursive function has two parts: the base case, and the recursive case. The recursive case is when the function calls itself in the program. The base case is when the function doesn’t call itself again … so it prevents the infinite loop. In general, when programming and thinking recursively, our main task and challenge will consist of establishing the base case and describing the recursive case to find the solution of our problem.

Let’s explain this with a simple mathematical example. I’m going to show how with a recursive function we can calculate a number to a power. This is our function:

As you can see in the last image, we can assign easy what is our recursive case (the function calls itself) and our base case (condition that breaks the function called). Now, let’s see how the recursion works when we want to use this code to calculate 10 power 3. With this case we have this:

Values to evaluate in our function:
  float x = 10
  float y = 3

  
  _pow_recursion(10, 3)---> Result must be 1000

So, how do we get to that programming solution. First, just take it step-by-step and break down the problem into smaller self-similar problems. So, it is important to understand how do we found that y = 0 is our base case. If we use that example to find out the power of a number, we found this:

Breaking the problem in smaller similar problems:
 10³ = 10² x 10
 10² = 10 x 10
 10 = 10

 10⁰ = 1 ---> Here we see that the problem doesn't exist anymore

With the example we can see that there is a pattern and when that pattern breaks is where we can figure out what is our base case that will cut the recursion call of the same function.

Let’s apply this with the same example but seeing how the stack works. Remember that stack is a space in memory where operations are stored in LIFO order (last in — first out).

As you can see in the last picture, the stack will keep storing recurse case until it find the base case. Then, it will solve all the stacks that were pending for execution and will goes down like a waterfall until the stack is over and give the right answer.

Five steps if you want a recursive solution

1. Determine the size of the problem.
2. Define bases cases.
3. Decompose the computational problem into self-similar subproblems of smaller size, and possibly additional different problems.
4. Define recursive cases by relying on induction and diagrams.
5. Test the code.

“Science is much more than a body of knowledge. It is a way of thinking.” — Carl Sagan

Finally I strongly recommend you watch these videos. These professors explains very well the recursion theory:

• What on Earth is Recursion? — Computerphile
• Recursion ‘Super Power’ (in Python) — Computerphile