CPSC 131 –
Intro. to Computer Programming II
Dongsheng Che
Department of Computer Science
East Stroudsburg University
Recursion (Chapter 13 )
Dongsheng Che
Department of Computer Science
East Stroudsburg University
Recursion
➢ Recursion is a basic programming technique you can use in Java,
in which a method calls itself to solve some problem.
➢ A method that uses this technique is recursive.
➢ Many programming problems can be solved only by recursion,
and some problems that can be solved by other techniques are
better solved by recursion.
General format
if (some easily-solved condition) { // base case
solution statement
} else { // general case
recursive function call
}
static int factorial(int n) {
if (n == 0 || n == 1) { // base case
return 1;
} else { // Generic case
return n * factorial(n - 1);
}
Successful recursion
Every recursive call must simplify the computation in some
way
There must be special cases to handle the simplest
computations directly
A list of problems using recursion
Factorial/Power
Palindrome
Fibonacci
Towers of Hanoi
Tree Drawing Problem
Queens
Permutation
Calculating Factorial
Solution 1:
Factorial without
Recursion
Solution 2:
Factorial using
recursion
Understand how factorial works
Another view on recursive n!
Hands-on Exercise (Rec_Summation)
Complete the method Sum_Rec. using recursive approach to add numbers
(1+2+…+upperbound). Run the program to print out the results.
The Palindrome Problem
Problem: Test whether a sentence is a palindrome
Palindrome: A string that is equal to itself when you reverse
all characters
➢ A man, a plan, a canal – Panama!
➢ Go hang a salami, I’m a lasagna hog
➢ Madam, I’m Adam
Illustration on palindrome problem
Program Demos
• The palindrome problem
The Fibonacci Number
Fibonacci sequence: Sequence of numbers defined by
f1 = 1
f2 = 1
fn = fn-1 + fn-2
First ten terms:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Fibonacci recursive implementation
Fibonacci recursion tree
Program Demos
• Fibonacci number
Efficiency of Recursion
Occasionally, a recursive solution runs much slower
than its iterative counterpart.
In most cases, the recursive solution is only slightly
slower.
In some cases, the recursive solution is very slow.
Redundant computation
Exponential execution time (O(2^n))
Fibonacci loop implementation
Time complexity:
Linear time (O(n))
Towers of Hanoi Problem
The objective is to move the stack of n disks to another rod, in
their original order. Only one disk may be moved at a time,
and a disk may never be placed on top of a smaller disk.
[Link]
1206/lectures/intro-to-recursion/
Recursive approach
1. Recursively Move N-1 disk
from source to Auxiliary peg.
2. Move the last disk from source
to destination.
3. Recursively Move N-1 disk
from Auxiliary to destination
peg.
Recursive algorithm
TOH Implementation
Program Demos
• Towers of Hanoi
Hands-on Exercise (Rec_ReverseString)
Complete the method reverseString. Using a
recursive approach to return a reversed string of
a given input string. Run the program to print
out the results.
Drawing Tree Problem
Drawing Tree Problem
N=0 N=1 N=2
Drawing Tree Stem
cx = x + [Link](a) * branchRadius
cy = y + [Link](a) * branchRadius
where a - Current angle of the stem
[Link](x, y, cx, cy);
(cx, cy)
a=90
(x, y)
Drawing Tree Branches
Middle:
tree(n-1, cx, cy,
a + bendAngle,
branchRadius * (1-branchRatio));
Left:
tree(n-1, cx, cy, Right:
a + bendAngle - branchAngle,
branchRadius * branchRatio); tree(n-1, cx, cy,
a + bendAngle + branchAngle,
(cx, cy) branchRadius * branchRatio);
(x, y)
Program Demos
• Drawing Tree Problem
Eight Queens Problem
Problem: position eight queens on a chess board so that
none of them attacks another according to the rules of
chess
A solution:
Backtracking on 4X4 Queen
1
3
?
Backtracking on 4X4 Queen (cont.)
1
?
1
4
2
?
Backtracking on 4X4 Queen (cont.)
1
4
1
3
4-queens search tree
Backtracking
Check consistency
Backtracking solution
Program Demos
• Eight Queen Problem
Permutations
Permutations abcd abdc acbd acdb adbc adcb
for ‘abcd’ bacd badc bcad bcda bdac bdca
cabd cadb cbad cbda cdab cdba
dabc dacb dbac dbca dcab dcba
Permutations abc acb Permutations ab
for ‘abc’ bac bca for ‘ab’ ba
cab cba
Permutations a Permutations
for ‘a’ for ‘’
Pseudocode for permutation
1
2
3
4
5
Permutation Implementation
e.g.:permutation(“b”, “acd”)
• permutation(“ba”, “cd”)
• permutation(“bc”, “ad”)
• Permutation(“bd”, “ac”)