Recursion

Note:
(*) Means that students are required to understand essential features only (the problem explaination, definitions, the outline of algorithms…), not in details.

5.1. Recursive definition

Wikipedia: “A recursive definition or inductive definition is one that defines something in terms of itself (that is, recursively). For it to work, the definition in any given case must be well-founded, avoiding an infinite regress”.
A recursive definition consists of at least 2 parts:

1) A base case (anchor or the ground case) that does not contain a reference to its own type.
2) An inductive case that does contain a reference to its own type.
For example: Define the set of natural numbers

5.2. Recursive program/algorithm

A recursive program/algorithm is one that calls itself again.
There are three basic rules for developing recursive algorithms.
• Know how to take one step.
• Break each problem down into one step plus a smaller problem.
• Know how and when to stop.

public static void convertToBin(int decimalNum)
{ int quotient = decimalNum / 2;        // One step
     int remainder = decimalNum % 2;   // One step
     if (quotient > 0)
{convertToBin(quotient); // smaller problem
}
System.out.print(remainder); // after all recursive calls have been
// made last remainder printed first
}

5.3. Recursion application

Recursive definitions are used in defining functions or sequences of elements
Purpose of recursive definition:

Generating a new elements
Testing whether an element belongs to a set (*)

(*) The problem is solved by reducing it to a simpler problem

Example – factorial calculation

5.4. Method calls and recursion implementation

How does recursion actually work?

Each time a method is called, an activation record (AR) is allocated for it. This record usually contains the following information:

Parameters and local variables used in the called method.
A dynamic link, which is a pointer to the caller's activation record.
Return address to resume control by the caller, the address of the caller’s instruction immediately following the call.
Return value for a method not declared as void. Because the size of the activation record may vary from one call to another, the returned value is placed right above the activation record of the caller.

Each new activation record is placed on the top of the run-time stack
When a method terminates, its activation record is removed from the top of the run-time stack
Thus, the first AR placed onto the stack is the last one removed

Creating an activation record whenever a method is called allows the system to handle recursion properly. Recursion is calling a method that happens to have the same name as the caller. Therefore, a recursive call is not literally a method calling it-self, but rather an instantiation of a method calling another instantiation of the same original. These invocation are represented internally by different activation records and are thus differentiated by the system.

5.5. Direct recursion

5.5.1. Tail recursion

There is only one recursive call at the very end of a method implementation

class Main
{static void tail(int n)
{if(n >0)
{ System.out.print(n + " ");
tail(n-1);
}
}
public static void main(String [] args)
{tail(10);
System.out.println();
}
}

Output: 10 9 8 7 6 5 4 3 2 1

5.5.2. Non-Tail recursion

The recursive call is not at the very end of a method implementation

public class Main
{public static void reverse() throws Exception
{char ch = (char) System.in.read();
if(ch != '\n')
{reverse();
System.out.print(ch);
}
}
public static void main(String [] args) throws Exception
{System.out.println("\nEnter a string to be reversed:");
reverse();
System.out.println("\n");
}
}

Running of the program:

5.6. Convert recursion implementation to iterative implementation using stack

public static void nonRecursiveReverse() throws Exception
{MyStack t = new MyStack();
char ch;
while(true)
{ch = (char) System.in.read();
if(ch == '\n') break;
t.push(ch);
}
while(!t.isEmpty())
System.out.print(t.pop());
}

5.7. Indirect recursion

If f() calls itself, it is direct recursive
If f() calls g(), and g() calls f(). It is indirect recursion. The chain of intermediate calls can be of an arbitrary length, as in:

f() -> f1() -> f2() -> ... -> fn() -> f()

Example: sin(x) calculation

5.8. Nested recursion

5.9. Excessive recursion

The tree of calls for fibo

5.10. More Examples

The Tower of Hanoi

Rules:

Only one disk may be moved at a time.
Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
No disk may be placed on top of a smaller disk.

Source: http://en.wikipedia.org/wiki/Hanoi_tower

void moveDisks(int n, char fromTower, char toTower, char auxTower)
{if (n == 1) // Stopping condition
Move disk 1 from the fromTower to the toTower;
else
{moveDisks(n - 1, fromTower, auxTower, toTower);
move disk n from the fromTower to the toTower;
moveDisks(n - 1, auxTower, toTower, fromTower);
}
}

Drawing fractals

von Knoch snowflakes

Divide an interval side into three even parts
Move one-third of side in the direction specified by angle

Turn to the right 60° (i.e., turn –60°) and go forward one-third of side
Turn to the left 120° and proceed forward one-third of side
Turn right 60° and again draw a line one-third of side long

private void drawFourLines(double side, int level, Graphics g) {
if (level == 0) {
// arguments to sin() and cos() must be angles given in radians,
// thus, the angles given in degrees must be multiplied by PI/180;
pt.x = ((int)(Math.cos(angle*Math.PI/180)*side)) + currPt.x;
pt.y = ((int)(Math.sin(angle*Math.PI/180)*side)) + currPt.y;
g.drawLine(currPt.x, currPt.y, pt.x, pt.y);
currPt.x = pt.x;
currPt.y = pt.y;
}
else {
drawFourLines(side/3.0,level-1,g);
left (60);
drawFourLines(side/3.0,level-1,g);
right(120);
drawFourLines(side/3.0,level-1,g);
left (60);
drawFourLines(side/3.0,level-1,g);
}
}

5.11. Recursion vs. Iteration

Some recursive algorithms can also be easily implemented with loops

When possible, it is usually better to use iteration, since we don’t have the overhead of the run-time stack (that we just saw on the previous slide)

Other recursive algorithms are very difficult to do any other way

5.12. Back tracking

In solving some problems, a situation arises where there are different ways leading from a given position, none of them known to lead to a solution. After trying one path unsuccessfully, we return to this crossroad and try to find a solution using another path. However, we must ensure that such a return is possible and that all paths can be tried. This technique is called backtracking. This technique is used in artificial intelligence, and one of the problems in which backtracking is very useful is the n-queens problem

Each choice leads to another set of choices. Make one choice and continue. If you reach a dead end, go back to previous choice and try next alternative.
putQueen(row)
for every position col on the same row
if position col is available
place the next queen in position col;
if (row < n)
putQueen(row+1);
else success;
remove the queen from position col;
source -

CF Department

vuongpnse02164

Thứ Tư, 31 tháng 10, 2012