FCDS
Programming II
Lecture 5: Recursion
Recursion
• recursion: The definition of an operation in terms of itself.
• Solving a problem using recursion depends on solving
smaller occurrences of the same problem.
• recursive programming: Writing methods that call themselves to
solve problems recursively.
• An equally powerful substitute for iteration (loops)
• Particularly well-suited to solving certain types of problems
Exercise
• (To a student in the front row)
How many students total are directly behind you in your "column" of the
classroom?
• You have poor vision, so you can
see only the people right next to you.
So you can't just look back and count.
• But you are allowed to ask
questions of the person next to you.
• How can we solve this problem?
(recursively )
The idea
• Recursion is all about breaking a big problem into smaller occurrences
of that same problem.
• Each person can solve a small part of the problem.
• What is a small version of the problem that would be easy to answer?
• What information from a neighbor might help me?
Recursive algorithm
• Number of people behind me:
• If there is someone behind me,
ask him/her how many people are behind him/her.
• When they respond with a value N, then I will answer N + 1.
• If there is nobody behind me, I will answer 0.
Recursion and cases
• Every recursive algorithm involves at least 2 cases:
• base case: A simple occurrence that can be answered directly.
• recursive case: A more complex occurrence of the problem that cannot be
directly answered, but can instead be described in terms of smaller
occurrences of the same problem.
• Some recursive algorithms have more than one base or recursive case, but all
have at least one of each.
• A crucial part of recursive programming is identifying these cases.
Recursion in Java
• Consider the following method to print a line of * characters:
// Prints a line containing the given number of stars.
// Precondition: n >= 0
public static void printStars(int n) {
for (int i = 0; i < n; i++) {
System.out.print("*");
}
System.out.println(); // end the line of output
}
• Write a recursive version of this method (that calls itself).
• Solve the problem without using any loops.
• Hint: Your solution should print just one star at a time.
A basic case
• What are the cases to consider?
• What is a very easy number of stars to print without a loop?
public static void printStars(int n) {
if (n == 1) {
// base case; just print one star
System.out.println("*");
} else {
...
}
}
Handling more cases
• Handling additional cases, with no loops (in a bad way):
public static void printStars(int n) {
if (n == 1) {
// base case; just print one star
System.out.println("*");
} else if (n == 2) {
System.out.print("*");
System.out.println("*");
} else if (n == 3) {
System.out.print("*");
System.out.print("*");
System.out.println("*");
} else if (n == 4) {
System.out.print("*");
System.out.print("*");
System.out.print("*");
System.out.println("*");
} else ...
}
Handling more cases 2
• Taking advantage of the repeated pattern (somewhat better):
public static void printStars(int n) {
if (n == 1) {
// base case; just print one star
System.out.println("*");
} else if (n == 2) {
System.out.print("*");
printStars(1); // prints "*"
} else if (n == 3) {
System.out.print("*");
printStars(2); // prints "**"
} else if (n == 4) {
System.out.print("*");
printStars(3); // prints "***"
} else ...
}
Using recursion properly
• Condensing the recursive cases into a single case:
public static void printStars(int n) {
if (n == 1) {
// base case; just print one star
System.out.println("*");
} else {
// recursive case; print one more star
System.out.print("*");
printStars(n - 1);
}
}
• The real, even simpler, base case is an n of 0, not 1:
public static void printStars(int n) {
if (n == 0) {
// base case; just end the line of output
System.out.println();
} else {
// recursive case; print one more star
System.out.print("*");
printStars(n - 1);
}
}
Recursive tracing
• Consider the following recursive method:
public static int mystery(int n) {
if (n < 10) {
return n;
} else {
int a = n / 10;
int b = n % 10;
return mystery(a + b);
}
}
• What is the result of the following call?
mystery(648)
A recursive trace
mystery(648):
int a = 648 / 10; // 64
int b = 648 % 10; // 8
return mystery(a + b); // mystery(72)
mystery(72):
int a = 72 / 10; // 7
int b = 72 % 10; // 2
return mystery(a + b); // mystery(9)
mystery(9):
return 9;
Recursive tracing 2
• Consider the following recursive method:
public static int mystery(int n) {
if (n < 10) {
return (10 * n) + n;
} else {
int a = mystery(n / 10);
int b = mystery(n % 10);
return (100 * a) + b;
}
}
• What is the result of the following call?
mystery(348)
A recursive trace 2
mystery(348)
int a = mystery(34);
• int a = mystery(3);
return (10 * 3) + 3; // 33
• int b = mystery(4);
return (10 * 4) + 4; // 44
• return (100 * 33) + 44; // 3344
int b = mystery(8);
return (10 * 8) + 8; // 88
• return (100 * 3344) + 88; // 334488
• What is this method really doing?
Exercise (Sum of 1 to N)
• Consider the problem of computing the sum of all the
numbers between 1 and any positive integer N
• This problem can be recursively defined as:
• The summation could be implemented recursively as
follows:
// This method returns the sum of 1 to num
public int sum(int num)
{
int result;
if (num == 1)
result = 1;
else
result = num + sum(n-1);
return result;
}
Sum of 1 to N
Exercise (Factorial)
• Write a recursive method that computes the factorial of a number n
• Note that:
1! = 1
2! = 1* 2
3! = 1* 2 * 3
4! = 1* 2 *3 * 4
…..
n! = 1* 2 *3 * 4 * ….* n
Example
class TestFact {
static int fact (int n) {
if (n == 1) Stop Condition
return 1 ;
else Recursive Step
return n * fact (n-1) ;
}
public static void main (String [ ]
args) {
System.out.println (“Factorial
of 3 is “+ fact(3));
System.out.println
(“Factorial of 4 is “+ fact(4));
System.out.println
(“Factorial of 5 is “+ fact(5));
}
Tracing the Recursive Method by Frames
6
3
int fact (int n) {
if (n == 1)
return 1 ;
else 2
return 3 *
fact (2); int fact (int n) {
} 2 if (n == 1)
return 1 ;
else 1
return 2 *
fact (1); int fact (int n) {
} 1 if (n == 1)
return 1 ;
else
return n *
fact (n-1);
}
Exercise (Power)
• Write a recursive method pow accepts an integer base and exponent
and returns the base raised to that exponent.
• Example: pow(3, 4) returns 81
• Solve the problem recursively and without using loops.
class TestPower {
static int power (int x, int y) {
if (y == 0) Stop Condition
return 1 ;
else
if (y == 1) Stop Condition
return x ;
else
return x * power (x, y-1)Recursive
; Step
}
public static void main (String [ ] args) {
System.out.println (“ 2 to power of
2 is “+ power(2,2));
}
}
Tracing the Recursive Method by Frames
9 3 2
int power (int x, int y) {
if (y == 0)
return 1 ;
else
if (y == 1)
return x ;
else 3 1
return 3 *
power (3,1) ; int power (int x, int y) {
} 3 if (y == 0)
return 1 ;
else
if (y == 1)
return 3 ;
else
return x *
power (x,y-1) ;
}
Exercise (Fibonacci Numbers)
• Write a recursive method that computes the nth Fibonacci number,
where n >=1
• Note:
fibo (1) = 1
fibo (2) = 1
fibo (3) = 2
fibo (4) = 3
fibo (5) = 5
…..
class TestFibo {
static int fibo (int n) {
if (n == 1) Stop Condition
return 1 ;
else
if (n == 2)
Stop Condition
return 1 ;
else
return fibo (n-2) + fibo (n-1)
Recursive Step;
public static void main (String [ ] args) {
System.out.println (“ Fibonacci of
4 is “+ fibo(4));
}
}
3
Tracing by Frames
4
3
int fibo (int n) { 2
if (n == 1) int fibo (int n) {
return 1 ; if (n == 1) int fibo (int n) {
else return 1 ; if (n == 1)
if (n == 2) else return 1 ;
return 1 ; if (n == 2) else
else return 1 ; if (n == 2)
return fibo (2)+ else return 1 ;
fibo(3); return fibo (1)+ else
} 1 2 fibo(2); return fibo (n-
} 1 1 2)+ fibo(n-1);
2 }
int fibo (int n) { 1
if (n == 1) int fibo (int n) {
return 1 ; if (n == 1)
else return 1 ;
if (n == 2) else
return 1 ; if (n == 2)
else return 1 ;
return fibo (n- else
2)+ fibo(n-1);
return fibo (n-
} 2)+ fibo(n-1);
}
Exercise (Palindrome)
• Write a recursive method isPalindrome accepts a String and
returns true if it reads the same forwards as backwards.
• isPalindrome("madam") true
• isPalindrome("racecar") true
• isPalindrome("step on no pets") true
• isPalindrome("able was I ere I saw elba") true
• isPalindrome("Java") false
• isPalindrome("rotater") false
• isPalindrome("byebye") false
• isPalindrome("notion") false
Exercise solution
// Returns true if the given string reads the same
// forwards as backwards.
// Trivially true for empty or 1-letter strings.
public static boolean isPalindrome(String s) {
if (s.length() < 2) {
return true; // base case
} else {
char first = s.charAt(0);
char last = s.charAt(s.length() - 1);
if (first != last) {
return false;
} // recursive case
String middle = s.substring(1, s.length() - 1);
return isPalindrome(middle);
}
}
Exercise solution 2
// Returns true if the given string reads the same
// forwards as backwards.
// Trivially true for empty or 1-letter strings.
public static boolean isPalindrome(String s) {
if (s.length() < 2) {
return true; // base case
} else {
return s.charAt(0) == s.charAt(s.length() - 1)
&& isPalindrome(s.substring(1, s.length() - 1));
}
}
Towers of Hanoi
• The Towers of Hanoi is a puzzle made up of three vertical
pegs and several disks that slide onto the pegs
• The disks are of varying size, initially placed on one peg
with the largest disk on the bottom with increasingly
smaller ones on top
• The goal is to move all of the disks from one peg to
another under the following rules:
• Move only one disk at a time
• A larger disk cannot be put on top of a smaller one
Towers of Hanoi
Original Configuration Move 1
Move 2 Move 3
Towers of Hanoi
Move 4 Move 5
Move 6 Move 7 (done)
Towers of Hanoi
• An iterative solution to the Towers of Hanoi is quite
complex
• A recursive solution is much shorter and more elegant
• See SolveTowers.java
• See TowersOfHanoi.java
//********************************************************************
// SolveTowers.java
// Demonstrates recursion.
//********************************************************************
public class SolveTowers
{
//-----------------------------------------------------------------
// Creates a TowersOfHanoi puzzle and solves it.
//-----------------------------------------------------------------
public static void main(String[] args)
{
TowersOfHanoi towers = new TowersOfHanoi(4);
towers.solve();
}
}
Output
//********************************************************************
// SolveTowers.java Author: Lewis/Loftus
// Move one disk from 1 to 2
Move one disk from 1 to 3
// Demonstrates recursion.
Move one disk from 2 to 3
//********************************************************************
Move one disk from 1 to 2
public class SolveTowers
Move one disk from 3 to 1
{ Move one disk from 3 to 2
//-----------------------------------------------------------------
Move one disk from 1 to 2
// Creates a TowersOfHanoi puzzle and solves it.
Move one disk from 1 to 3
//-----------------------------------------------------------------
public static voidMove
mainone disk from
(String[] args)2 to 3
{ Move one disk from 2 to 1
Move one
TowersOfHanoi towers disk
= new from 3 to (4);
TowersOfHanoi 1
Move one disk from 2 to 3
towers.solve();Move one disk from 1 to 2
}
Move one disk from 1 to 3
}
Move one disk from 2 to 3
//********************************************************************
// TowersOfHanoi.java
//
// Represents the classic Towers of Hanoi puzzle.
//********************************************************************
public class TowersOfHanoi
{
private int totalDisks;
//-----------------------------------------------------------------
// Sets up the puzzle with the specified number of disks.
//-----------------------------------------------------------------
public TowersOfHanoi(int disks)
{
totalDisks = disks;
}
//-----------------------------------------------------------------
// Performs the initial call to moveTower to solve the puzzle.
// Moves the disks from tower 1 to tower 3 using tower 2.
//-----------------------------------------------------------------
public void solve()
{
moveTower(totalDisks, 1, 3, 2);
}
continued
continued
//-----------------------------------------------------------------
// Moves the specified number of disks from one tower to another
// by moving a subtower of n-1 disks out of the way, moving one
// disk, then moving the subtower back. Base case of 1 disk.
//-----------------------------------------------------------------
private void moveTower(int numDisks, int start, int end, int temp)
{
if (numDisks == 1)
moveOneDisk(start, end);
else
{
moveTower(numDisks-1, start, temp, end);
moveOneDisk(start, end);
moveTower(numDisks-1, temp, end, start);
}
}
//-----------------------------------------------------------------
// Prints instructions to move one disk from the specified start
// tower to the specified end tower.
//-----------------------------------------------------------------
private void moveOneDisk(int start, int end)
{
System.out.println("Move one disk from " + start + " to " +
end);
}
}
