Sunday, September 18, 2011

Recursion - How to approach in algorithms

package main.java.concepts;

public class Recursion {

	// Every recursion should have the following characteristics.
	//
	// 1) A simple base case which we know a solution for and a return value. This is to break the recursion loop. This is generally a hardcoded known value for fxn(0) or fxn(1) or fxn(null)
	// 2) A way of getting our problem closer to the base case. I.e. a way to chop out part of the problem to get a somewhat simpler problem.
	// 3) A recursive call which passes the simpler problem back into the method.
	
	// approach
	// solve for f(0) or f(1) or f(null)
	// solve for f(2)
	// solve for f(3) using f(2) - this will give a logic for sub-problem
	// generalize for f(n)
	// test
	
	// recusrion vs iteration
	
	// recursive - calls itself (possibly more than once), with different parameters, and defines an exit clause that is guaranteed to be reached
	// iterative - includes a loop, which iterates a pre-determined number of times, or checks for an exit clause every time through. 
	
	// 1) recursion uses more memory = Each recursive call adds a new layer to the stack, which means that if your algorithm has O(n) recursive calls then it uses O(n) memory. 
	// 	- Recursion may be slower, and use greater resources, because of the extra function calls. 
	// 2. Recursion may lead to simpler, shorter, easier-to-understand functions. 
	
	// use iteration or recursion 
	// with which it is easy to implement, maintain the code in a few months or years (and should not blow up performance) 
	// If you run into performance issues, then profile your code, and then and only then look into optimizing by moving over to an iterative implementation. 
	// You may want to look into memoization and dynamic programming.
	
	// when easy to use recursion - 
	// “Design an algorithm to compute the nth	”; “Write code to list the first n	”; “Implement a method to compute all	”; 
	
	public static void main(String[] args) {
		Recursion r = new Recursion();
		r.myCounter(4);
	}

	// recursive method is comprised of an if-else statement where the base case
	// returns one value and the non-base case(s) recursively call(s) the same
	// method with a smaller parameter or set of data.

	public void myCounter(int c) {
		if (c == 0)
			return;
		System.out.println(c);
		myCounter(--c);
		System.out.println(c);

	}

	// Note: Forgetting the base case leads to infinite recursion. It won't run
	// an infinite loop, instead, it will eventually run out of stack memory and
	// get a run-time exception called a stack overflow. The size of a
	// stack may be quite large, but limited. Therefore too deep recursion can
	// result in Stack Overflow. recursion has a serious disadvantage of using
	// large amount of memory

	public int myFactorial(int n) {
		if (n == 1)
			return 1;
		else {
			return (n * (myFactorial(n - 1)));
		}
	}
}

1 comment: