There is a programming joke that goes “In order to understand recursion, one must first understand recursion.” In this article, we are going to explore the concept of recursion and its counterpart iteration.
What is recursion?
In its essence, recursion is the process of repeating items in a self-similar way.
In mathematics, it a means of solving a function by repeatedly applying a routine operation to the known values of the function. The idea of recursion is to reduce a problem into simpler version of itself.
How is recursion used in programming?
In programming, recursion is a technique where a function calls itself. A function calling itself can have unintended consequences, such as an infinite recursion. Thus, it is important to establish one or more base cases that the program can solve in order to prevent it from occurring. In addition, the program must solve the same problem with some other input with the goal of simplifying the larger problem input.
But first…iteration
Before demonstrating how recursion works, we must first understand how to solve a problem iteratively. If you have worked with loops before, you are definitely familiar with iteration. To refresh, iteration is the process of repeating a routine until a certain condition is met. Let’s start with a multiplication problem.
Solving iteratively
Say that our goal is to multiply a times b. Multiplying a times b is equivalent to adding the value a to itself b times. The mathematics it will be expressed as this:
a * b = a + a + a + … + a
In Ruby we can solve this problem iteratively with a function like this:
In this function, the program will run as long as the value b greater than zero. Inside the while loop, two things are happening: First, the value is a going to be accumulated by itself with each passing loop and be stored in the result variable. Second, the value b is going to be decremented by 1 with each passing loop. Once b reaches zero, the condition is met and the program will display the result value in the console.
Solving recursively
Lets look at our multiplication problem again and try to solve it from a different angle. In the previous example, we have declared that:
a * b = a + a + a + … + a
Since we know that the consecutive accumulative a’s represent adding the value a to itself b times. We can reduce our problem by expressing it like this:
a * b = a + a * (b - 1)
Writing the problem like this would give us a base case. When the value b is equal to one, the value of a will be just a.
With this function, we have a condition that checks for our base case, b equal to one. When b is greater than one, the program will call itself b minus one times, and repeat the process until b reaches our base case. Each passing will accumulate the result in the variable a. When the program reaches the base case, it will return the sum of its subsequent loops to the console.
