How to Recursion
Recursion is very useful, most iterative solutions (using only loops) will be much more complex than a recursive solution. Recursion allows to decompose a problem into conquerable subproblems and consider in each step only one such subproblem. Understanding recursion is the key to solving many exercises in Eprog.
Code example from geeksforgeeks
Recursion Introduction
Recursion is the process of using a method within itself directly or indirectly. Whenever method call can result into the method itself being called again before the original method call is finished then we have recursion. Recursion is counterintuitive at first but recursion is not confined to the space of computers and appears in nature quite often. Take the vegetable romanesco broccoli for example which features a recursive pattern.
One can see that the smaller structures seem to be an exact copy of the the larger structure they are a part of. One might now argue that this pattern does not infinitely many times reproduce. This however is also not the case with computers as they have limited memory as well. They might simulate recursion to a more extreme level but in the end we are limited to a finite result.
Another example for this recursive pattern is the nautilius shell. Many more examples exist in nature. It seems that building structures recursively often being easier than non-recursively is something nature has found way before humans even existed.
Recursion Introduction
At first we must understand how recursion works before we start implementing problems using recursion. Let us start with a simple code example and analyse its behaviour when executed.
int factorial(int n) {
if(n == 0) {
return 1;
}
return n * factorial(n - 1) ;
}
When this function is executed, for example using n = 2 then the method executions are inserted into each other. One can think of the method call as a placeholder for the code within the method.
int factorial(2) {
if(2 == 0) {
return 1;
}
return 2 * factorial(1) ;
}
int factorial(1) {
if(1 == 0) {
return 1;
}
return 1 * factorial(0) ;
}
int factorial(0) {
if(0 == 0) {
return 1;
}
}
One can see that the method call factorial(0) is terminates first, then the method call factorial(1) terminates and finally factorial(2) terminates. This splits recursion into an opening phase where method calls are made and a closing phase where the method are terminated in reverse order.
The Power of Recursion
While you have been reading this introduction to recursion you may have asked yourself what the code to the left does. What it does exactly is not as important, for people interested in the problem being solved I recommend reading the corresponding Wikipedia article. One however might notice more importantly that the code makes no use of recursion and that the code is very long and hard to understand.
To the right one can now see a recursive solution also from geeksforgeeks. It is apparent that this solution is much easier to implement. The reason why we have such a big discrepancy between the iterative and the recursive solution is because the problem is recursive in nature. We find a repeatable process we can apply to reduce the problem to smaller subproblems. Whenever this can be done we must think of recursion.
Recursive Definitions
The first and most simple recursive programs are programs which implement mathematical recursive definition of functions and hence the recursive relation is directly apparent from the given code. These recursive definitions however allow us to introduce the main components of every recursion.
fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)
Base cases
For a recursion to terminate we must specify a base case which does not itself call the method recursively. Otherwise the recursion will go on forever (until memory runs out). Bases cases are subproblems which cannot be split into smaller subproblems anymore. They are the atomic subproblem which all results build upon. The Fibonacci sequence has two bases cases, n = 0 and n = 1 as can be seen in the recursive function definition above. This is an important point. Many recursions have multiple bases cases and not just one. One must be careful when choosing the base cases to make sure that all base cases are covered.
fib(0) = 0
fib(1) = 1
Recursive Step
In a next step we must think about how the solution of a problem arises from a solution of a subproblem. For this purpose it is useful to compute some examples on a sheet of paper to see how the solutions are computed and then find possible subproblems.
It is important that subproblems are themselves an instance of the general problem but with "smaller" parameters. Smaller in the sense that the subproblem does not require the solution of the problem to be solved. In the Fibonacci sequence example we are given the problem to find Fib(n), i.e. the n-th Fibonacci number, and the recurrence relation in the function decomposes this into finding the solutions to the subproblems Fib(n - 1) and Fib(n - 2) first. One can see that Fib(n) and Fib(n - 1) are instances of the same underlying general problem just that one parameter is smaller than the other.
fib(n) = fib(n - 1) + fib(n - 2)
Recursive Problems
The key to solving problems using recursion is to first find the base cases and then finding a recursive step. Implementing the recursive solution should be the smaller part of the work when you solve a problem using recursion. It is important that you solve some small problem instances on paper and try to identify subproblems in your solution steps. Once these subproblems have been found you must connect them to find a generalised problem solution. Every recursion must first check if the given parameters represent a base case and then if that is not the case do the recursive step.
If you attempt to directly implement a recursion you will often fail to do so because you are not yet sure what the subproblems are and they will not appear to you during programming but rather when you solve some simple examples on paper.
An Example
To the right one can see a typical problem description of an exercise which tasks us to implement a solution to a problem using recursion. We hence in a first step look at a simple example which will help us find the recursive solution.
Take the string s = "example" and c = 'e' as an example. The char 'e' appears twice in the string s. We first look at the first character of s and find that it is the same character as is stored inside c. We can hence add +1 to the count. How do we continue? We just look at the second, third, fourth, fifth, sixth and finally seventh character. We overall add +1 twice to the count and hence the result is 2.
We now must determine first the base case from this example. It would make sense to either choose the empty string "" as a base case always containing zero characters equal to c or alternatively to choose a single character and check if it is the same character as c. The first base case is preferred as it does not depend on c and always returns the same value.
In a next step we want to find the subproblem. After having found that the first character of s is indeed equal to the character stored in c, we continue with s' = "xample" and c = 'e'. Computing the result of number of characters equal to c in s' and adding +1 to it (the first character was equal to c) we get the desired solution. This is the recursive step. All that is left is to implement the solution. The subproblem is given to us using s.substring(1, s.length()) or equivalently s.substring(1) which is s without character 0. The solution to s.substring(1) can be found in the same way as to the solution for s. This process continues until we arrive at a base case where the solution is hardcoded.
Given a String s determine the number of times the character stored in c appears inside of s using recursion.
Edge cases
The example solution is almost correct. One thing is missing. Try to think about it before reading the next sentences.
We must always check that all parameters are well-defined according to our program, if s is null then calling the substring method on it results in an exception because null references no object. Hence this would have to be added. Such problem instances are called edge cases and they are often forgotten, but for correctness of the solution always needed.