Recursion is a programming fundamental that is highly used in algorithms. Simply put, recursion is the ability of a method to call itself. When a method calls itself it stacks up and uses the LIFO (Last-in First-out) approach. It’s the same concept as a stack of plates. Let’s see the following scenario:
To summarize the above figure, remember that the last element that is inserted in the stack will be the first one to be removed. That’s why LIFO.
To memorize and really understand the LIFO approach, just remember that when you stack up plates, you can’t get the plate at the bottom. Instead, it’s much easier and more suitable to get the first one at the top of the stack. The methods are stacked exactly in the same way!
FILO (First-in Last-out) has the same result as LIFO. It basically means that the first plate to go on the stack will be the last one to go out.
To summarize the above figure, the first plate that is inserted in the stack will be the last one to be removed.
Another point to keep in mind is that what can be done with recursion can also be done with loopings too and vice-versa.
Let’s see a simple Java example using this concept:
public class Recursion {
public static void main(String[] args) {
System.out.println(getNumber(0));
}
static int getNumber(int number) {
if (number > 5) { // #A
return number;
}
return getNumber(number + 1); // #B
}
}
Code analysis:
#A: This “if” is the condition that is necessary to break the recursion looping. This basically means that when the number parameter is greater than 5, the recursion looping will stop. This is also called the base case in recursion.
#B: Notice that the getNumber method is invoking itself and it’s adding up 1 to the parameter. This means that every time the method getNumber is invoked the number parameter will be summed with 1. This method is invoked the first time with 0 as the number and it’s stacked until it’s 6 as you can see in the following image:
Seeing LIFO/FILO in practice
When we sum the numbers the order that methods are invoked recursively doesn’t really matter. However, if we want to print numbers in order that changes completely. Let’s see LIFO/FILO happening in practice:
public class NumbersRecursion {
public static void main(String[] args) {
showNumbers(0);
}
static void showNumbers(int number) {
if (number == 5) {
return;
}
showNumbers(number + 1);
System.out.print(number + " ");
}
}
Output:
4 3 2 1 0
Notice that the number was printed in reverse order. That’s because the method is recursively stacked as you can see in the debugging images:
When all methods were invoked, notice that the variable number is 5:
When all methods were invoked and the methods are going out of the stack the variable number is 3:
Therefore, it’s like the recursive call will intercept this method invocation and wait until the last recursive method is called to be the first out of the stack. That’s why the first number to be printed is 4!
Recursion Tree with Fibonacci
The Fibonacci algorithm is a classic one every developer does during their college studies. Solving the Fibonacci algorithm with recursion though is not so efficient it uses a lot more memory and it’s more complex.
If you forgot what is the Fibonacci algorithm, the goal is to basically sum the previous number with the next one starting with 0 and 1. For example, by starting the algorithm receiving 0 and 1 we would have the following numbers:
0, 1, 2, 3, 5, 8, 13, 21, 34, 55…
A way to solve this problem in maths is to use the following formula:
Fn = Fn-1 + Fn-2
Considering that maths is the basis of programming and it’s what is behind it, we can replicate that in code by using recursion.
Our goal then is to pass a number to the Fibonacci algorithm and get the result using recursion.
public class FibonacciRecursion {
public static void main(String[] args) {
System.out.println(fibonacci(3));
}
static int fibonacci(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
In the above code, notice that there are two recursive calls. The first one subtracts 1 to n and the second subtracts 2 to n. When that happens, the following recursive tree will be created:
Notice how the tree above was created. The Fibonacci method is invoked from F(3) and the recursion starts. Then F(2) is invoked, then F(1). Remember that F(1) matches the base condition, therefore, it will return 1.
Then, the invocation returns to F(2) and invokes F(0), it also matches the base condition returning 0.
From F(0), it goes back to F(2), then F(3). Then F(3) invokes the second method F(1) and it returns 1. That’s why the result is 2.
The final order of the method invocations is the following:
F(3), F(2), F(1), F(2), F(0), F(2), F(3), F(1)
Notice that the bigger the number n is the more method invocations we will have. The growth is exponential.
Big(O) Notation for Recursive Fibonacci
Let’s see now how this algorithm performs:
Time complexity: T(2^N) which means when N is 3, the time complexity is 9 – very slow
Space complexity: O(N) which means the sum of the invoked methods in the stack
Simply put, the Big(O) notation measures the performance and space used to execute an algorithm. You must be wondering why the space complexity is different from the time complexity, let’s explore that.
The time complexity will be always exponential and that’s not performant. This happens because, in terms of time, the recursive invocations will have to go through all the recursive trees.
The space complexity is different though. To explain what is space complexity, it’s basically the space in memory that an algorithm will use.
Remember that the recursive method invocations are stored in a stack? So, what happens is that when F(3) invokes F(2) and F(1) – F(1) and F(2) will be popped out from the stack. The key to understanding it in simple words is that the leftmost methods will be invoked and then popped out from the stack. Therefore, no matter how big the tree might become, the space will be always (n).
