View RSS Feed

sunde887

Recursion

Rating: 2 votes, 4.00 average.
by , 06-20-2011 at 04:39 AM (4846 Views)
Recursion:


Recursion is defined as:
1. the act or process of returning or running back
2. logic, maths the application of a function to its own values to generate an infinite sequence of values. The recursion formula or clause of a definition specifies the progression from one term to the next, as given the base clause f (0) = 0, f ( n + 1) = f ( n ) + 3 specifies the successive terms of the sequence f ( n ) = 3 n

In this article, I hope to make the reader have a basic understanding of what recursion is, and how it works. When programming there are indeed different types of recursion, there are iterative recursive processes, and simple recursive processes. Shortly I will explain the two in more depth, and provide some examples of the two.

Recursion is simple, but can get quite complex. You are creating a method that is defined in terms of it's self. One of the simplest examples of a recursive process is calculating the factorial of a number. The factorial of a number is pretty easily understood and recognized. The factorial of some number n, is 1 * 2 * 3 ... n-1 * n. This can be directly translated into a recursive process quite easily. You can define the recursion in words like so:

The factorial of a number n is either:
1. if n is 0, the factorial is 1
2. otherwise perform n * n - 1

The first part in this simple definition is known as the termination condition. The termination condition is what ends the process. If not included it will cause infinite recursion. Much like a standard for loop has a condition, recursion does as well. If you created the following for loop
Java Code:
for(int i = 0;; ++i)
It would loop indefinitely, since you provided no end condition. One of the key things to remember when writing a recursive method is to figure out what should end the method. How long should it continue calling itself recursively before finding an answer?

Let's turn the definition of a factorial above into a running program. The method is simple and will return the int result of the computation.
Java Code:
public class Factorial{
  /**
   * The method below computes the factorial of some number, n.
   * @param int
   */
  public int factorial(int n){
    if(n == 0) //this is the termination condition
      return 1; // when the condition is reached, 1 is returned.
    else{
      return n * factorial(n - 1); //notice the recursive call here
    }
  }
  public static void main(String[] args){
    Factorial f = new Factorial();
    int n = f.factorial(10);
    System.out.println(n);
    n = f.factorial(5);
    System.out.println(n);
  }
}
This is a very basic recursive method which I am using as an example. The applications of recursion can get much more complicated, and I intend to show some more powerful uses of recursion(although not too complex). When this method runs it first checks the termination condition, if it's met, the method returns an answer. If the condition is not met, it adds something to the stack and calls a new method.

In java, when a method encounters another method, it gets pushed to the top of the stack and temporarily stops the original method until the new method is completed. Once the method being called finishes, the program picks up from where it left off. Since this simple recursive method calls itself n times, it pushes n items onto the stack, it continues pushing method calls onto the stack until the termination condition is met. Then it calculates the remaining things on the stack. An example easily illustrates how this works:
Java Code:
factorial(5) 
5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1 * factorial(0) //Termination condition
5 * 4 * 3 * 2 * 1 * 1
5 * 4 * 3 * 2 * 1
5 * 4 * 3 * 2
5 * 4 * 6
5 * 24
120
The method reaches the final step
Java Code:
return n * factorial(n - 1)
. so n is put on the stack and attempts to multiply, but it reaches a new method call which is pushed onto the stack and begins running. This repeats until the method reaches the termination condition and then it goes back and finishes evaluating all the multiplications on the stack.

Another, possibly more elegant way to compute the factorial of some number requires that you keep a "Running total" of the current factorial. This method contains steps, where each step contains all the information to calculate the answer at that step. If you were to stop in the middle of the method and print the results, you could instantly restart from where you were. In the previous example, you would have to start the calculation from the beginning.

This is known as an iterative recursive process, and here is what it looks like
Java Code:
public class Factorial{
	public int factorial(int n){
		return factorial(n, 1);
	}
	public int factorial(int n, int soFar){
		if(n == 0) return soFar;
		return factorial(n - 1, (soFar * n));
	}
	public static void main(String[] args){
		Factorial f = new Factorial();
		int n = f.factorial(10);
		System.out.println(n);
		n = f.factorial(5);
		System.out.println(n);
	}
}
This method overloads factorial so you can pass in a single argument and that argument gets forwarded to another version of factorial(an iterative version).

I believe in java both methods take up the same space. Either way the method is being continuously called. However; in other languages, like scheme, the amount of space required between the two methods is quite dramatically different. The amount of space for the first(recursive) method is O(n), the space depends on the amount of times the method is called. The second approach(iterative) has O(1) in terms of space. It's constant, at each step the value is known. Here is what the space required would look like in a language like scheme.
Java Code:
factorial(5, 1)
factorial(4, 5)
factorial(3 20)
factorial(2 60)
factorial(1 120)
factorial(0, 120)
120
Each step "remembers" the value calculated so far.

The amount of things recursion can do is vast. I believe it's almost safe to say that recursion can accomplish anything in programming(notice I said almost, I'm sure there there things recursion is incapable of).

Recursion can do things like, sum an array, count the amount of items in said array, and do many other array based processing tasks. Here are a few

Java Code:
interface Transformer{
	int transform(int n);
}
Java Code:
class Mult implements Transformer{
	int factor;
	public Mult(int factor){
		this.factor = factor;
	}
	public int transform(int n){
		return factor * n;
	}
}
Java Code:
public class ArrayUtil{
	private Transformer t;
	
	public ArrayUtil(Transformer t){
		this.t = t;
	}
	public int sumArray(int[] arr){
		return sumArray(0, arr);
	}
	public int sumArray(int index, int[] arr){
		if(index == arr.length) return 0;
		return arr[index] + sumArray(index + 1, arr);
	}
	
	public int countArray(int[] arr){
		return countArray(0, arr);
	}
	public int countArray(int index, int[] arr){
		if(index == arr.length) return 0;
		return 1 + countArray(index + 1, arr);
	}
	
	public void transformArray(int[] arr){
		transformArray(0, arr);
	}
	public void transformArray(int index, int[] arr){
		if(index == arr.length) return;
		arr[index] = t.transform(arr[index]);
		transformArray(index + 1, arr);
	}
	public static void main(String[] args){
		Transformer x = new Mult(10);
		int[] y = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		ArrayUtil au = new ArrayUtil(x);
		System.out.println(au.sumArray(y));
		System.out.println(au.countArray(y));
		au.transformArray(y);
		for(int i = 0; i < y.length; ++i){
			System.out.print(y[i] + ", ");
		}
		System.out.println();
	}
}
This may require a bit of explaining, the transformer interface and Mult class must be in different files, and it allows you to transform the array in many different ways. For example, if you wanted to add x to each element you can simply make the following class
Java Code:
public class Adder implements Transformer{
  int amount;
  public Adder(int amount){
    this.amount = amount;
  }
  public int transform(int n){
    return n + amount; 
  }
}
You would then pass in a reference to this class to the ArrayUtil constructor. This uses the strategy pattern to make transform quite easily extensible to anything you can think of.

The transform method is the only thing new here, it simply forwards to a so called "alien method," the exact behavior is unknown, it can change to whatever the Transformer t requires it to do. The method really isn't too challenging though, it simply moves through the array recursively transforming each element of the array.


There is many more complex things that can be done with recursion, and this "complex" example, is really quite trivial.

You can do things from animating recursively, solving puzzles recursively, and drawing fractals recursively. If you would like to learn a lot more about recursion, I highly recommend you check out the following two books(both of which are freely available online).

The first is "How to Design Programs," available at HTDP.org

The second is "Structures and Interpretation of Computer Programs," available at http://www-mitpress.mit.edu/sicp/

I hope this article was helpful and helped you learn something. Feel free to criticize any claims I may have made or offer corrections.

Submit "Recursion" to Facebook Submit "Recursion" to Digg Submit "Recursion" to del.icio.us Submit "Recursion" to StumbleUpon Submit "Recursion" to Google

Updated 06-20-2011 at 04:48 AM by sunde887

Tags: None Add / Edit Tags
Categories
Uncategorized

Comments