Recursion
- Recursive definition
- Method calls and recursion implementation
- Anatomy of a recursive call
- Tail recursion
- Non-tail recursion
- Indirect recursion (*)
- Nested recursion (*)
- Excessive recursion
- Backtracking (*)
- Reading at home
Note:
(*) Means that students are required to understand essential features only (the problem explaination, definitions, the outline of algorithms…), not in details.
(*) 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 infiniteregress”.
- 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
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.
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
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(); } } |
5.5.2. Non-Tail recursion
The recursive call is not at the very end of a method implementationpublic 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"); } } |
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:
- 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.
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
- 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
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
