[Yayoi Kusama Infinity Mirrored Room - Filled with the Brilliance of Life 2011/2017 Tate Presented by the artist, Ota Fine Arts and Victoria Miro 2015, accessioned 2019 © YAYOI KUSAMA]
*What is Recursion *
At some point or another you will come across the concept of recursion. Recursion is a method in which you are able to solve larger problems by breaking them down into smaller instances of the same problem.
What is strikingly different and often confusing about recursion is that a recursive function actually calls itself within its own function which for myself and many others causes a lot of confusion about what is actually going on. Together we are going to break down a problem with recursion so we can see what is going on.
Our Example
For our example we will create a factorial function. A factorial sequence is the product of all positive integers less than or equal to a given positive integer. For example, factorial(3) would be 6 as factorial(3) = 3 x 2 x 1 = 6 similarly factorial(5) = 5 x 4 x 3 x 2 x 1 = 120 .
Factorials are useful for problems where you have to evaluate permutations and combinations. They can be used to answer questions such as “How many different ways can we arrange a class seating plan” but for this post we will keep it short and sweet.
The Code
public int factorial (int num){
if(num == 1 ){
return 1;
}
else{
return num * factorial (num - 1);
}
}
The Base Case
First things first, vital to any recursive function is something called the base case. As the function calls itself, how does it know when to stop? . Well that is what we have the base case for. In our example our base case is if(num == 1){return 1). What that does is, as we call our function again and again with return num * factorial(num - 1) we are edging closer and closer to num == 1 as we are calling factorial(num - 1 ) over and over again . Without the base case in place the function would call itself infinitely and result in a stack overflow exception.
Lets get into an example
Now what happens next can cause a lot of confusion. When return num * factorial (num - 1); is reached the computer will also call itself again but this time with (num-1) while it is in the middle of trying to work out what factorial(num) is. To solve this the computer will throw the first call into a stack and move onto the next call . It will do this over and over again with each successive call decreasing num by 1 until it reaches the base case and stops. You can think of this as the computer stacking a pile of plates where each call places another plate on the pile and the only way to access the pile is but taking the top plate of the pile.
Where the magic happens
The best way to visualise this is with an actual example. Lets solve for Factorial(3). Armed with our base case and our pile of plates (Stack). We will initially ask our computer to solve factorial(3). We check our base case firstly num != (does not equal) 1 so we move deeper into the block. The function is now called again with num reduced by one and the last call factorial(3) added to the stack. Now Factorial(2) is called and again we check the base case . No. Not there yet so again we delve deeper into the block , factorial(2) is added to the top of the stack. Finally on the next call we reach the base case and we do not go deeper into the block.
So how do we reach the answer
To reach the last plate in our pile we must first pick up the first plate to get to the second and so on. At the stop of our stack we have Factorial(1) which returns 1 as this is our base case. The computer now passes this to the parent call or the plate below in our stack of plates . It now has a look at Factorial(2). We already know that Factorial(1) = 1 the computer can use this answer to solve factorial(2) which is 2 * Factorial(1) = 2 .
Finally we get to the bottom and all plates have been removed besides one Factorial(3). As we have already solved what factorial(2) is using the previous calls we can answer what Factorial(3) is using the previous calls. Factorial(3) = 6.
You've reached the base case
If you've made it this far , I hope you have a better understanding of how a simple recursive function works. Reading and writing your own recursive functions take a lot of time and practice but understating the basics is a great place to start.
[Yayoi Kusama Infinity Mirrored Room - Filled with the Brilliance of Life 2011/2017 Tate Presented by the artist, Ota Fine Arts and Victoria Miro 2015, accessioned 2019 © YAYOI KUSAMA]