Go to www.google.com and type in recursion, then click search…
You will notice the Google search engine attempts to redirect you by using the famous “Did you mean” followed by the word recursion, exactly as you spelt it. Although this is somewhat of a poor joke on Google’s behalf it can have a function in this tutorial. A function or method is said to be recursive when it calls itself, a famous example of this and probably one of the most common problems is that of implementing recursion in factorials.
import java.io.*;
public class Main {
static int factorial(int n) {
if (n <= 1) {
return 1;
}
else {
return n * factorial(n-1); //function calls itself here
/* n * n-1 = factorial of n
* Example: 5
* 5x4x3x2x1 = 120
*/
}
}
public static void main(String[] args) throws IOException {
// TODO code application logic here
BufferedReader inKb = new BufferedReader (new InputStreamReader (System.in));
System.out.println ("Enter a number and I will calculate the factorial:");
int num = Integer.parseInt(inKb.readLine());
System.out.println("The factorial is:" + factorial(num));
}
}
Now then, as one can see, in order to calculate the factorial of the inputted number, the function called factorial calls itself if the number given is over 1. Why is the first if statement necessary?
Comment out the first if statement of the factorial function and the else and just leave return n * factorial (n-1);
If you had run the program, your compiler should have given you a java.lang.StackOverflowError, the simple reason for this is the function entered an infinite loop. In order to use the wonders of recursion properly one very important element of recursion must be implemented and understood.
When does the function stop calling itself?
The solution to this is creating what is known as the base case.
The base case is an instance of the problem you can solve without making a recursive function call. So in the case of the factorial example, 1x1 is 1. Therefore our base case is going to be
if (n <= 1) {
return 1;
}
Another important fact about the base case is that when you call the recursive function, you must get closer to the base case otherwise if the base case is not reached, then it is just dead code and an infinite loop will occur again.
Another rather important thing to note about recursion is do not use recursion with global variables, the changing of a global variable can give you a different output, declare variables in the function itself so that if you run factorial (5), it will give you the output of 120 each time.
Another classic example of recursion is the Fibonacci sequence, coded below:
import java.io.*;
public class Main{
public static void main (String[] args) throws IOException{
BufferedReader inKb = new BufferedReader (new InputStreamReader (System.in));
System.out.println("Enter a number to calculate fibonacci value of that value:");
int num = 0;
int fibnum = 0;
num = Integer.parseInt(inKb.readLine());
fibnum = fibonacci(num);
System.out.println("the fibonacci value of " + num + "th is "+ fibnum);
}
static int fibonacci(int n) {
if (n <= 2) {
return 1;
//the base case:If k <= 2 then fib(k) = 1.
}
else {
return fibonacci(n-1) + fibonacci(n-2);
//if n > 2 then fibonnaci(n) = fibonacci(n-1) + fibonacci(n-2)
}
}
}
If you run the code, it will become evident that certain numbers are calculated again such as fibonnaci(2), this leads to excessive computation whereby the algorithm will continue to calculate Fibonacci(2) as it is necessary.
There are some pitfalls to recursion such as:
• Not defining a base case, this will lead to the recursive function calling itself repeatedly resulting in a stack overflow or segfault error.
• Recursion can use excessive amounts of space as variables are constantly being created (As I will demonstrate now.)
• Excessive computation, enter a very large number into the recursive factorial and see how long it takes.
However all of these problems with recursion can be solved with good coding techniques. The first problem of not defining a base case is merely the coder’s error however the last 2 problems can be solved if we use a technique called memoization.
Memoization (word stemming from memory optimization) is a technique that can be used to optimize the runtime of algorithms. In this case, we will use memoization to optimize the runtime of our fibonacci program. If one thinks about how the fibonacci sequence calculates the item at the nth position of the fibonacci sequence, as one can see from the image below, certain fibonacci numbers repeat.
Now if we implement memoization, the programmer will use an adequate data structure to store the numbers being calculated. In this case, we will use a treemap. What the coder then does is simply check if the data being calculated is in the data structure, if it is then simply return that value and if it is not then calculate the value using the given algorithm. In the case of the fibonacci sequence if values are stored and returned we can cut down a huge amount of computation time by return the value that was worked out before. This is demonstrated in the image below:
Here is the code for the fibonacci program with memoization:
package fibonacciexample;
import java.math.BigInteger;
import java.util.Map;
import java.util.TreeMap;
import java.io.*;
public class Main{
// Note: a treemap is used to store the fibonacci numbers that have already been calculated, also a biginteger is used to avoid loss of precision.
static Map<Integer, BigInteger> memo = new TreeMap<Integer, BigInteger>();
public static void main (String[] args) throws IOException{
BufferedReader inKb = new BufferedReader (new InputStreamReader (System.in));
System.out.println("Enter a number to calculate fibonacci value of that value:");
int num = 0;
int fibnum;
num = Integer.parseInt(inKb.readLine());
fibnum = fibonacci(num);
System.out.println("the fibonacci value of " + num + "th is "+ fibnum);
System.out.println ("The memoized calculation of that value is: " + memoizedFibonacci(num));
}
static int fibonacci(int n) {
if (n <= 1) {
return 1;
//the base case:If k <= 2 then fib(k) = 1.
}
else {
return fibonacci(n-1) + fibonacci(n-2);
//if n > 2 then fibonnaci(n) = fibonacci(n-1) + fibonacci(n-2)
}
}
static BigInteger memoizedFibonacci(int n)
{
if (n <= 1) return BigInteger.ONE;
if (memo.get(n) == null)
{
//If the element is not in the treemap, we then calculate it and add it.
memo.put(n, memoizedFibonacci(n-1).add(memoizedFibonacci(n-2)));
}
return memo.get(n); //return the treemap.
}
}
I hope you noticed the use of memoization affected the total computation time of the fibonacci algorithm tremendously,
Enter in a big number like 110, you should be kept waiting (I wait with my PC
) for the computer to work out the values, however if you then do the same however with using memoization, the calculation should be almost instant.memoization has one benefit:
- Memoization decreases the computation time of the optimized algorithm as it reduces the amount of calculation that is required by storing the calculated data into a data structure such as an array or treemap. The original runtime of the fibonacci sequence according to big-O notation is exponential time (O(n^n)) however with memoization the algorithm runs at linear time as we are returning O(n) in many cases.
and one drawback:
- Memoization requires more space as another data structure is needed to store the values already calculated, in the case of the fibonacci sequence not much more space is used however in many cases memoization takes up too much extra space when used to be practical.
In essence, when you use memoization you are trading time for space, you decrease the computation time of your algorithm but increase the amount of space in memory that your program uses. Memoization in general however is a very good tool for optimizing your algorithms!
I hope this tutorial has explained recursion and memoization to a considerable extent
Recursion truly is a powerful tool in computer programming however it can be very difficult at first to understand if a function is recursive, just ask yourself is there any need for this function to repeat?
I hope you all have enjoyed my tutorial. I hope its not too shabby, its my first tutorial.
Thanks, vortex.
This post has been edited by v0rtex: 20 April 2011 - 10:01 PM
MultiQuote
thanks 
| 