Recursion is property of self-similarity.

i.e. something consists of smaller simpler versions of itself

Many examples in nature and in mathematics

Recursive Java method is one that activites (calls) itself.

Be aware of indirect recursion, e.g. two methods each call the other. More generally, chain of method calls in which a method already in the chain is called again.

A recursive method must consider three notions:
1. base case (aka stopping case). We have reached the "simplest" version, so no further recursion
2. recursive step. We have not yet reached the "simplest" version, so recurse.
3. some form of "added value" (something besides the recursive call itself happens at this step).

Recursion can be used as alternative to loops (iteration).

Recursion can always be mimicked using stacks.

n! = 1*2*3*...*n

Give recursive definition

n! =	undefined	if n < 1
	1 		if n == 1
	n * (n-1)!	otherwise

Write two versions of method public static int factorial(int n), iterative and recursive.

Fibonnacci sequence starts with 1, 1 and thereafter each number is sum of previous two.

Sequence of length 7 is: 1, 1, 2, 3, 5, 8, 13

Give recursive definition of n'th value in Fibonacci sequence:

fib(n) =	undefined		if n < 1
		1			if n==1 or n==2
		fib(n-1)+fib(n-2)	otherwise

Write two versions of method public static int fib(int n), iterative and recursive. It returns n'th value in Fibonacci sequence.

(draw trees to trace an example, e.g. fib(6))

Given:

class Node
{
	Object data;
	Node next;
}

List length can be defined recursively as:

length(head) is: 	0 			if head==null (base case)
			length(head.next)+1 	otherwise. (recursive step)

Since public length() method does not take a parameter and the recursive version requires a parameter, the usual strategy is to define a "recursive partner" or "recursive helper"

public int length()
{
	return lengthRecurse(head);
}
private int lengthRecurse(Node cursor)
{
	if (cursor == null)
		return 0;
	else
		return lengthRecurse(cursor.next)+1;
}

Pseudo-code or mathematical function definition first, then java code

// Forward
public void print()
{
	return printRecurse(head);
}
private void printRecurse(Node cursor)
{
	if (cursor != null)
	{
		System.out.print(cursor.data);
		printRecurse(cursor.next);
	}
}
// Backward
public void printRev()
{
	return printRevRecurse(head);
}
private void printRevRecurse(Node cursor)
{
	if (cursor != null)
	{
		printRevRecurse(cursor.next);		
		System.out.print(cursor.data);
	}
}
// Forward then Backward
public void printTwoWay()
{
	return printTwoWayRecurse(head);
}
private void printTwoWayRecurse(Node cursor)
{
	if (cursor != null)
	{
		System.out.print(cursor.data); // forward list
		printTwoWayRecurse(cursor.next);
		System.out.print(cursor.data); // backward list
	}
}

IMPORTANT: none of these recursive methods use loops (for, while). Iteration is handled by the act of recursion. You must use an "if" statement to recognize base case, however.

Tail recursion: when the recursive step is the very last operation in the method. Nearly all compilers will recognize this and try to convert it to a loop. The method printRecurse() exemplifies this.

Write method public void removeEnd() and recursive partner to remove last node of list, given only reference to head. Don't forget special case where head is only node in list.

Write method public void insertEnd(Object obj) and recursive partner to insert node containing obj as last node of list, given only reference to head. Don't forget special case where list is empty.

Write method public void reverse() and recursive partner to reverse a list by reversing its links, given only reference to head. Don't forget special cases where list is empty or where head is only node in list.

When method is called (recursive or not),
1. arguments are evaluated and added to calling methods activation record
2. calling method is suspended and address of next instruction is kept.
3. activation record is created for called method. Contents described below.
4. activation record is pushed on runtime (execution) stack.
5. execution resumes at starting address of called method.
6. if it calls another method, this process is recursively carried out

When called method is finished,
7. its activation record is popped from runtime stack
8. calling method retrieves return value (if any)
9. execution resumes at the address stored in step 2.

Typical activation record contents:
1. values of actual parameters (arguments)
2. a slot for the return value (if any) of the method
3. instruction address in caller where execution is to resume at end of call
4. space for called method's local variables
5. pointer to calling methods activation record (link in "call chain" for stacking/unstacking)

Proving that recursion will terminate is similar to proving that loop will terminate.

Proving that recursion is correct is similar to proving that a loop is correct:

• assuming that preconditions are true, show that post conditions are true after one iteration.
• Show that if true after n iterations will also be true after n+1 iterations. Proof by induction.

Maze and other "state search" problems (e.g. chess)

• Computation here is a journey with some goal.
• Some sequences of steps lead to this goal and others don't.
• Decision points are encountered along the way.
• At each, a number of options are available.
• You decide on one, and if it later turns out to have been incorrect, you backtrack to the decision point and try a different option.
• If all decisions turn out to be incorrect, you backtrack to the previous decision point. If there is no previous decision point (e.g. you are back at the starting point), there is no solution.
• This same process is followed at every decision point, so this is naturally recursive.

What is the distance from Baltimore to Miami, measured along the coastline?

Depends on how closely you "hug" the coastline. The closer you look at it (e.g. smaller the scale of the map), the longer the distance becomes. If you zoom in on even a short stretch of apparently straight coastline, you will see that it is jaggy too! Then zoom in recursively on a short stretch of THAT, and again you will find it to be jaggy.

[ Lectures | CSC 132 | Peter Sanderson | Computer Science | SMSU ]

Peter Sanderson ( PeteSanderson@smsu.edu )