What is recursion?

Introduction

I clearly remember the first time I saw the recursion concept in Holberton. We were learning how to program in C language and one of the hardest exercises that I had made until the moment we started learning recursion, was one exercise called print number.

The exercise consisted in create a C function that prints an integer following these requirements:

• We could only use putchar function to print.

• We were not allowed to use long.

• We were not allowed to use arrays or pointers.

• We were not allowed to hard-code special values.

It was a hard exercise, and it took me 38 lines of code to arrive to the solution. When I learned recursion, I made the same exercise but I took me only 12 lines of code. In that moment was when I realize how powerful and important could be understanding the concept of recursion and how to apply it.

Recursion

Generally speaking, recursion is the concept of well-defined self-reference. It is the determination of a succession of elements by operating on one or more preceding elements according to a rule or a formula involving a finite number of steps.

In computer science, recursion is a programming technique using function or algorithm that calls itself one or more times until a specified condition (base case) is met at which time the rest of each repetition is processed from the last one called to the first.

Base Case

One critical requirement of recursive functions is the termination point or base case. Every recursive program must have a base case to make sure that the function will terminate. Missing base case results in unexpected behavior.

The Call Stack

Recursive functions use something called “the call stack.” When a program calls a function, that function goes on top of the call stack. This is similar to a stack of books. You add things one at a time. Then, when you are ready to take something off, you always take off the top item.

In order to get a better understanding I would like to explain how a recursive function works with an example:

Pow function implemented with recursion in C language

At first let’s identify the recursion in our function:

This function receives two parameters of type float, x as the base and y as the exponent.

In order to analyze a specific case let’s work with the values of x = 3.0 and y = 4.0. The following diagram explains how our function works:

In this example, the first call to the function is _pow_recursion(3.0,  4.0). After that, the Base Case (y == 0) condition is evaluated but this time y (4.0) is not equal to 0.0 so the second conditional is evaluated, like y y is a positive number (y > 0) the second condition is never fulfilled. So the second call to our function is _pow_recursion(3.0,  3.0) because x still being x = 3.0 but y = 4.0 – 1.0 = 3.0, and the function continues calling itself decreasing the value of y until it becomes in 0.0 and the base case is fulfilled and the recursion terminates.

Once the Base Case is fulfilled, the function returns the value of 1 and the program continue performing all the pending calculations since the program starts (with the value of x = 3.0 and 4.0) and this is how our function get the result of 3.0 to the power of 4.0 is equals to 81 is reached, this is the concept of “the call stack” that we have seen above.