Recursion in computer programming is the process of a function calling itself. It can be used to solve complex problems by breaking them down into smaller, more manageable ones.
And although that may seem simple enough, recursion is actually quite complicated to understand, and it’s especially a challenge for CS beginners. But when you are really able to grasp the inner-workings of this concept, you’ll see that recursion is an art.
Let’s see an example. The code below is a recursive implementation of the Fibonacci Sequence, an infinite mathematical sequence that starts with 1, 1, where every number after is equal to the sum of the previous two.
The Fibonacci Sequence (embedded wikipedia link if you want to learn more about it): 1, 1, 2, 3, 5, 8, 13, 21, 34,…
This function takes only one argument, n, and returns the n-th element in the Fibonacci Sequence. If n equals 1 or 2 (first two elements), the function returns 1. Otherwise, the function will call itself and return the sum of the previous two Fibonacci numbers.
If recursion is still relatively foreign to you, it may be hard to wrap your head around how telling the function to call itself works. We are used to giving specific, detailed instructions to the computer when programming, but in this case, we’re kinda just telling the computer to “figure it out”.
To make it easier to understand, here’s a graphical representation of what the function will do when we search for fibonacci(5):
Because the initial n is not equal to 1 or 2, the function returns f(n-2)+ f(n-1), so f(5) becomes f(3) + f(4).
The function then calls itself at f(3). Under the same process, because n≠1, 2, f(3) becomes f(2) + f(1). The whole equation becomes f(2) + f(1) + f(4).
This time, both f(2) and f(1) will return 1, so f(3) = 1 + 1. Using the same logic, f(4) then becomes f(2) + f(3) → f(2) + f(1) + f(2) → 1 + 1 + 1. Thus, f(5) is equal to 1 + 1 + 1 + 1 + 1 = 5.
This function only takes three lines of code, but is able to represent one of the most interesting patterns in mathematics. That is the beauty of recursion.
