What is Recursion?

Everything a programmer should know about recursion

In this blog I will explain the concept of recursion and show some examples in C.

Recursion, by definition, is “when a thing is defined in terms of itself.” In this case we refer to mathematical or programmatic functions. With respect to a programming function, recursion occurs when a function calls itself within its own definition. It calls itself over and over again until a basic condition is met that breaks the loop.

You might be thinking, how is that different from iteration. Think of iteration as something that builds up to a solution and recursion breaking down a problem into smaller instances of itself order to get to the solution. In other words, think of recursion as a method that simplifies the problem into smaller sub problems.

There are 2 main parts of a recursive function; the base condition and the recursive call. The base condition is important because without it, the function would theoretically repeat forever (in the application there would be what is known as a “stack overflow” to stop the repetition which we will touch on a little later). Below is an example of a simple recursive function.

Examples

1. Factorial

The factorial operation is a perfect candidate for recursion because it is a problem that can easily be broken down into smaller similar problems.

5! = 5 * 4 * 3 * 2 * 1

So if we want to calculate the factorial of 5, we can think of it as multiplying 5 by the factorial of 4:

5! = 5 * 4!

Similarly, to calculate the factorial of 4, we multiply 4 by the factorial of 3:

4! = 4 * 3!

So on, then we can define the following:

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

And so… Let’s implement a factorial function in C!

This recursive function calculates the factorial of its integer argument. Think through what happens when you pass this function an argument of 3:

factorial (3) returns 3 * factorial (2)
factorial (2) returns 2 * factorial (1)
factorial (1) is the case condition and returns 1

Once the base condition is met, all the factorial () calls will return in succession to give us an answer of 6.

3 * (2 * (1)) = 6

Now let’s see what happens on the stack while this recursive function is running.

2. Power function with recursion

We can see that it is a recursive power function called _pow_recursion that receives two integers, x and y, and returns an integer that is the result of x ^ y (x raised to y).

So what happens when we call the function with 2 and 3 as parameters:

_pow_recursion (2, 3)

In theory the following would be obtained:

(“x” = 2) and (“y” = 3) → (2³) that is (2 * 2 * 2) and the result is: 8

But really what happens, the function starts to “iterate” until the base condition is reached, which is y == 0 and for each “iteration” or “recursive call”, the function will put all the values ​​on the stack of the variables, as we saw in the previous example, each function call adds another layer to the stack.

The order of the stack grows from the bottom up and once we get to the _pow_recursion (2, 0) call, the variable satisfies the base condition or base case of if (y == 0) and:

1. The function will return 1, it will take this value, which is: _pow_recursion (2,0) = 1
2. It will calculate the requested operation: in this case multiply _pow_recursion (2,0) by “x”
3. The function will be equal to the result of the previous step, in this case
   if _pow_recursion (2,0) = 1 and “x” = 2, the result will be 2 and this is the value of the function in the next step.
4. The value of all the variables from the previous step will be put on the stack.
5. Given that the function _pow_recursion (2,0) * 2 = 2, the process will be repeated from step 2 until all the values ​​of the variables associated with this process leave the stack.

When we get to the last call to the function, all the recursive calls have returned, and finally the _pow_recursion (2, 3) function returns the value 8. The stack is now empty and our function is complete!

Read and Write

It takes some time to familiarise yourself with recursion but here are two skills that will come into use:

1. Reading Recursive Code: There are two things to look for. The base condition and the recursive case. What base condition are we looking for and how does the recursive case finally reach this result?
2. Write recursive code: change the mindset from looping to recursion. Recurrence in simple tasks that you would normally use loops for.

I hope this small article on recursion helps you in your programming journey and you find useful ways to implement it to become more efficient.