Recursion
This article is my own attempt to make you “aha” about recursion, let me know if I’ve been successful.
Definition of recursion
Recursion is a process that calls itself.
Nature itself is a brilliant example of recursion, think for instance at reproduction: individuals that are born from other individuals and so on.
Why is recursion worth knowing?
Because it’s everywhere and companies will ask you about it.
Despite recursion melts brains on daily basis all over the globe, it’s able to solve graph traversal problems in a much more readable and elegant way than its cousin iteration. By graph traversal problems I mean all problems that has to do with nested self-similar structures, such as searching inside the DOM object.
Essential parts of a recursive function
1. Base Case
The Base Case is the endpoint of any recursion, it’s always a conditional statement (often an if-clause). You can refer it as the rock bottom of the recursion.
2. Different inputs
By different inputs I mean that each recursive call has to have a different input, otherwise the Base Case will never be reached and you’ll fall into an infinite poop (loop of poop).
The Call Stack
Almost all programming languages implement recursion, to do so they use the so called Call Stack.
The Call Stack is the built-in data structure which manages function invocations.
The idea is that functions calls are pushed on top of the stack and as they return they are popped out off the stack.
Usually with recursion the same function is called over and over with different inputs and the Call Stack deepens until the last call hits the Base Case and so the results cascade back through previous call to the first one.
The Call Stack can become quite deep when a function invokes many other functions, or itself recursively.
If you are a web developer, as I pretend to be, you can use your browser to inspect the Call Stack (Developer tools > Sources).
Stack overflow
Stack overflow is a phenomenon which occurs when too many function calls get stacked on top of the Call Stack. It’s an indicator that something is wrong with your code.
Stack overflow happens when:
1. No Base Case
2. No return inside Base Case
3. Recursive call with same input
Factorial for teaching recursion
The first example I’ve ever seen in recursion was the mathematical factorial function.
The factorial function is simply multiplying descending numbers together.
fact(5) = 5 * 4 * 3 * 2 * 1
fact(4) = 4 * 3 * 2 * 1
fact(3) = 3 * 2 * 1
fact(2) = 2 * 1
fact(1) = 1
Did you noticed the recursive pattern?
fact(5) = 5 * fact(4)
fact(4) = 4 * fact(3)
fact(3) = 3 * fact(2)
fact(2) = 2 * fact(1)
fact(1) = 1
In a way you could say that each function call when returning fills in the blanck for its caller.
Helper method recursion
Helper method recursion is a noteworthy design pattern which helps you simplifying certain recursive solutions.
It works by defining an helper recursive function within another function. The outer function’s sole responsibility is to store some data and call the helper recursive inner function.
Imagine you want to collect all numbers from N down to 0 into an array, and you want to do it recursively.
Using pure recursion would be painful, because you should concatenate arrays returned from various recursive calls.
Using the helper method recursion simplifies things A LOT.
Look:
Fin
Hope you’ve enjoyed this article, if so leave comment! :D
