Page 1 of 1

Introduction to Recursion and Memoization with examples Rate Topic: ****- 1 Votes

#1 v0rtex  Icon User is offline

  • Caffeine: db "Never Enough!"
  • member icon

Reputation: 223
  • View blog
  • Posts: 773
  • Joined: 02-June 10

Posted 20 April 2011 - 07:11 AM

*
POPULAR

Introduction to Recursion and Memoization with Examples:

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.

Posted Image

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:

Posted Image

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 :D) 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


Is This A Good Question/Topic? 9
  • +

Replies To: Introduction to Recursion and Memoization with examples

#2 codewizard  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 16
  • Joined: 20-April 11

Posted 20 April 2011 - 01:10 PM

Thanks a lot, I was struggling with the concept of recursion but this tutorial cleared up all my questions, I was also unaware of memoization, Seems like a useful technique :)
Was This Post Helpful? 0
  • +
  • -

#3 v0rtex  Icon User is offline

  • Caffeine: db "Never Enough!"
  • member icon

Reputation: 223
  • View blog
  • Posts: 773
  • Joined: 02-June 10

Posted 20 April 2011 - 01:50 PM

Good to hear. :)
Was This Post Helpful? 0
  • +
  • -

#4 ivan.bisevac  Icon User is offline

  • New D.I.C Head

Reputation: 3
  • View blog
  • Posts: 2
  • Joined: 20-April 11

Posted 20 April 2011 - 05:15 PM

@v0rtex
You have error in code. It's in fibonacci example on 8th line. It gives allways output:

Quote

the fibonacci value of 0th is 1


There should be:
num = Integer.parseInt(inKb.readLine());


Simple but great tutorial.
Was This Post Helpful? 0
  • +
  • -

#5 v0rtex  Icon User is offline

  • Caffeine: db "Never Enough!"
  • member icon

Reputation: 223
  • View blog
  • Posts: 773
  • Joined: 02-June 10

Posted 20 April 2011 - 10:02 PM

Thanks a lot, I noticed that when I wrote the memoizationfibonacci code but didnt fix it in original :( thanks :)
Was This Post Helpful? 0
  • +
  • -

#6 cdog5000  Icon User is offline

  • D.I.C Head

Reputation: 11
  • View blog
  • Posts: 79
  • Joined: 31-October 09

Posted 21 April 2011 - 12:27 PM

Thanks a lot, I love tutorials like this that help me understand things that sometimes are very hard to explain. Especially when they do a good job of explaining it. Great job.
Was This Post Helpful? 1
  • +
  • -

#7 MrGreenforya  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 06-March 11

Posted 14 May 2011 - 12:27 PM

Such a thorough guide, love it! Learned about recursing sequences/series in pre-calc last week, and it had me confused but you cleared it all up now. Thanks so much!
Was This Post Helpful? 0
  • +
  • -

#8 Niha  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 42
  • Joined: 20-April 07

Posted 22 June 2011 - 04:50 AM

Awesome! I didn't know anything about recursion but I think I've got the hang of it now. But what does BigInteger.ONE refer to??
Was This Post Helpful? 0
  • +
  • -

#9 ivan.bisevac  Icon User is offline

  • New D.I.C Head

Reputation: 3
  • View blog
  • Posts: 2
  • Joined: 20-April 11

Posted 22 June 2011 - 04:56 AM

View PostNiha, on 22 June 2011 - 04:50 AM, said:

Awesome! I didn't know anything about recursion but I think I've got the hang of it now. But what does BigInteger.ONE refer to??

It's constant, look at: http://download.orac...BigInteger.html
Was This Post Helpful? 3
  • +
  • -

Page 1 of 1