Data Structures and
Algorithms
"
Recursion!
The Recursion Pattern"
• Recursion: when a method calls itself!
• Classic example--the factorial function:!
– n! = 1· 2· 3· ··· · (n-1)· n!
• Recursive definition:!
⎧ 1 if n = 0
f (n) = ⎨
⎩n ⋅ f (n − 1) else
Phạm Bảo Sơn - DSA
The Recursion Pattern"
• As a Java method:!
// recursive factorial function
public static int recursiveFactorial(int n) {
if (n == 0) return 1;
// base case
else return n * recursiveFactorial(n- 1); //
recursive case
}!
Phạm Bảo Sơn - DSA
Content of a Recursive
Method"
• Base case(s). !
– Values of the input variables for which we perform
no recursive calls are called base cases (there
should be at least one base case). !
– Every possible chain of recursive calls must
eventually reach a base case.!
• Recursive calls. !
– Calls to the current method. !
– Each recursive call should be defined so that it
makes progress towards a base case.!
Phạm Bảo Sơn - DSA
Visualizing Recursion"
Example recursion trace:
• Recursion trace!
return 4*6 = 24 final answer
• A box for each call
recursiveFactorial(4)
recursive call! call return 3*2 = 6
• An arrow from each recursiveFactorial(3)
call return 2*1 = 2
caller to callee! recursiveFactorial(2)
• An arrow from each call return 1*1 = 1
recursiveFactorial(1)
callee to caller call return 1
showing return value! recursiveFactorial(0)
Phạm Bảo Sơn - DSA
Example – English Rulers"
• Define a recursive way to print the ticks and
numbers like an English ruler:!
Phạm Bảo Sơn - DSA
A Recursive Method for
Drawing Ticks on an English
Ruler"
// draw a tick with no label
public static void drawOneTick(int tickLength) { drawOneTick(tickLength, - 1); }
// draw one tick
public static void drawOneTick(int tickLength, int tickLabel) {
for (int i = 0; i < tickLength; i++)
System.out.print("-");
if (tickLabel >= 0) System.out.print(" " + tickLabel);
System.out.print("\n");
}
public static void drawTicks(int tickLength) { // draw ticks of given length
if (tickLength > 0) { // stop when length drops to 0
drawTicks(tickLength- 1);
// recursively draw left ticks
drawOneTick(tickLength);
// draw center tick
drawTicks(tickLength- 1);
// recursively draw right ticks
}
}
public static void drawRuler(int nInches, int majorLength) { // draw ruler
drawOneTick(majorLength, 0);
// draw tick 0 and its label
for (int i = 1; i <= nInches; i++)
{
drawTicks(majorLength- 1);
// draw ticks for this inch
drawOneTick(majorLength, i);
// draw tick i and its label
}
}
!
!
! Phạm Bảo Sơn - DSA
Visualizing the DrawTicks
Method"
• An interval with a drawTicks (3 ) Output
drawTicks (2 )
central tick length L >1 drawTicks (1 )
is composed of the drawTicks ( 0 )
following:! drawOneTick (1 )
– an interval with a central drawTicks ( 0 )
drawOneTick (2 )
tick length L-1,!
drawTicks (1 )
– a single tick of length L,!
drawTicks (0 )
– an interval with a central drawOneTick (1 )
tick length L-1.! drawTicks (0 )
drawOneTick (3 )
drawTicks (2 )
(previous pattern repeats )
Phạm Bảo Sơn - DSA
Recall the Recursion Pattern"
• Recursion: when a method calls itself!
• Classic example--the factorial function:!
– n! = 1· 2· 3· ··· · (n-1)· n!
• Recursive definition:!
⎧ 1 if n = 0
f (n) = ⎨
⎩n ⋅ f (n − 1) else
• As a Java method:!
// recursive factorial function
public static int recursiveFactorial(int n) {
if (n == 0) return 1;
// base case
else return n * recursiveFactorial(n- 1);
// recursive case
}!
Phạm Bảo Sơn - DSA
Linear Recursion"
• Test for base cases. !
– Begin by testing for a set of base cases (there should be at
least one). !
– Every possible chain of recursive calls must eventually reach
a base case, and the handling of each base case should not
use recursion.!
• Recur once. !
– Perform a single recursive call. (This recursive step may
involve a test that decides which of several possible recursive
calls to make, but it should ultimately choose to make just
one of these calls each time we perform this step.)!
– Define each possible recursive call so that it makes progress
towards a base case.!
Phạm Bảo Sơn - DSA
A Simple Example of Linear
Recursion"
Algorithm LinearSum(A, n):! Example recursion trace:
Input: !
An integer array A and an call return 15 + A[4] = 15 + 5 = 20
integer n >= 1, such that A has LinearSum (A,5)
at least n elements! call return 13 + A[3] = 13 + 2 = 15
Output: ! LinearSum (A,4)
The sum of the first n integers in call return 7 + A [2 ] = 7 + 6 = 13
A! LinearSum (A,3)
if n = 1 then" call return 4 + A [1 ] = 4 + 3 = 7
return A[0]! LinearSum (A,2)
else" call return A[0] = 4
return LinearSum(A, n - 1) + A[n LinearSum (A,1)
- 1]!
!
Phạm Bảo Sơn - DSA
Reversing an Array"
Algorithm ReverseArray(A, i, j):!
Input: An array A and nonnegative integer
indices i and j!
Output: The reversal of the elements in A
starting at index i and ending at j!
if i < j then"
! !Swap A[i] and A[ j]!
! !ReverseArray(A, i + 1, j - 1)!
return!
Phạm Bảo Sơn - DSA
Defining Arguments for
Recursion"
• In creating recursive methods, it is important
to define the methods in ways that facilitate
recursion.!
• This sometimes requires we define additional
paramaters that are passed to the method.!
• For example, we defined the array reversal
method as ReverseArray(A, i, j), not
ReverseArray(A).!
Phạm Bảo Sơn - DSA
Computing Powers"
• The power function, p(x,n)=xn, can be defined
recursively:!
⎧ 1 if n = 0
p( x, n) = ⎨
⎩ x ⋅ p( x, n − 1) else
• This leads to a power function that runs in
O(n) time (for we make n recursive calls).!
• We can do better than this, however.!
!
Phạm Bảo Sơn - DSA
Recursive Squaring"
• We can derive a more efficient linearly
recursive algorithm by using repeated squaring:!
⎧ 1 if x = 0
⎪
! p( x, n) = ⎨ x ⋅ p( x, (n − 1) / 2) 2 if x > 0 is odd
⎪ p ( x , n / 2) 2
if x > 0 is even
⎩
• For example,!
24
= 2(4/2)2 = (24/2)2 = (22)2 = 42 = 16
25
= 21+(4/2)2 = 2(24/2)2 = 2(22)2 = 2(42) = 32
26
= 2(6/ 2)2 = (26/2)2 = (23)2 = 82 = 64
27
= 21+(6/2)2 = 2(26/2)2 = 2(23)2 = 2(82) = 128.!
Phạm Bảo Sơn - DSA
A Recursive Squaring
Method"
Algorithm Power(x, n):!
Input: A number x and integer n = 0!
Output: The value xn!
if n = 0 !then"
" "return 1!
if n is odd then"
! !y = Power(x, (n - 1)/ 2)!
" "return x · y ·y!
else"
! !y = Power(x, n/ 2)!
" "return y · y!
Phạm Bảo Sơn - DSA
Analyzing the Recursive
Squaring Method"
Algorithm Power(x, n):!
Input: A number x and
integer n = 0!
Output: The value xn! Each time we make a
if n = 0 !then" recursive call we halve the
value of n; hence, we make
" "return 1! log n recursive calls. That
if n is odd then" is, this method runs in
! !y = Power(x, (n - 1)/ 2)! O(log n) time.
" "return x · y · y!
else" It is important that we
used a variable twice here
! !y = Power(x, n/ 2)! rather than calling the
" "return y · y! method twice.
Phạm Bảo Sơn - DSA
•
Tail Recursion "
Tail recursion occurs when a linearly recursive method makes
its recursive call as its last step.!
• The array reversal method is an example.!
• Such methods can be easily converted to non-recursive
methods (which saves on some resources).!
• Example:!
Algorithm IterativeReverseArray(A, i, j ):!
Input: An array A and nonnegative integer indices i and j!
Output: The reversal of the elements in A starting at index i and
ending at j!
while i < j do"
!Swap A[i ] and A[ j ]!
!i = i + 1!
!j = j - 1!
return!
Phạm Bảo Sơn - DSA
Binary Recursion"
• Binary recursion occurs whenever there are
two recursive calls for each non-base case.!
• Example: the DrawTicks method for drawing
ticks on an English ruler.!
Phạm Bảo Sơn - DSA
A Binary Recursive Method for
Drawing Ticks"
// draw a tick with no label
public static void drawOneTick(int tickLength) { drawOneTick(tickLength, - 1); }
// draw one tick
public static void drawOneTick(int tickLength, int tickLabel) {
for (int i = 0; i < tickLength; i++)
System.out.print("-");
if (tickLabel >= 0) System.out.print(" " + tickLabel);
Note the two
System.out.print("\n");
}
public static void drawTicks(int tickLength) { // draw ticks of given length
if (tickLength > 0) { // stop when length drops to 0
recursive calls
drawTicks(tickLength- 1);
// recursively draw left ticks
drawOneTick(tickLength);
// draw center tick
drawTicks(tickLength- 1);
// recursively draw right ticks
}
}
public static void drawRuler(int nInches, int majorLength) { // draw ruler
drawOneTick(majorLength, 0);
// draw tick 0 and its label
for (int i = 1; i <= nInches; i++)
{
drawTicks(majorLength- 1);
// draw ticks for this inch
drawOneTick(majorLength, i);
// draw tick i and its label
}
}
!
!
! Phạm Bảo Sơn - DSA
Another Binary Recusive
Method"
• Problem: add all the numbers in an integer array A:!
Algorithm BinarySum(A, i, n):!
Input: An array A and integers i and n!
Output: The sum of the n integers in A starting at index i!
if n = 1 then"
" return A[i ]!
return BinarySum(A, i, n/ 2) + BinarySum(A, i + n/ 2, n/ 2)!
• Example trace:"
0, 8
0, 4 4, 4
0, 2 2, 2 4, 2 6, 2
0, 1 1, 1 2, 1 3, 1 4, 1 5, 1 6, 1 7, 1
Phạm Bảo Sơn - DSA
Computing Fibonacci
Numbers"
• Fibonacci numbers are defined recursively:!
F0 = 0
F1 = 1
Fi = Fi-1 + Fi-2 for i > 1.
• As a recursive algorithm (first attempt):!
Algorithm BinaryFib(k):
Input: Nonnegative integer k
Output: The kth Fibonacci number Fk
if k <= 1 then
return k
else
return BinaryFib(k - 1) + BinaryFib(k - 2)!
Phạm Bảo Sơn - DSA
Analyzing the Binary
Recursion Fibonacci Algorithm"
• Let nk denote number of recursive calls made by
BinaryFib(k). Then!
– n0 = 1 !!
– n1 = 1 !!
– n2 = n1 + n0 + 1 = 1 + 1 + 1 = 3 !!
– n3 = n2 + n1 + 1 = 3 + 1 + 1 = 5 !!
– n4 = n3 + n2 + 1 = 5 + 3 + 1 = 9 !!
– n5 = n4 + n3 + 1 = 9 + 5 + 1 = 15 !!
– n6 = n5 + n4 + 1 = 15 + 9 + 1 = 25 !!
– n7 = n6 + n5 + 1 = 25 + 15 + 1 = 41 !!
– n8 = n7 + n6 + 1 = 41 + 25 + 1 = 67.!
• Note that the value at least doubles for every other
value of nk. It is exponential!!
Phạm Bảo Sơn - DSA
A Better Fibonacci
Algorithm"
• Use linear recursion instead:!
Algorithm LinearFibonacci(k):!
Input: A nonnegative integer k!
Output: Pair of Fibonacci numbers (Fk, Fk-1)!
if k = 1 then"
" "return (k, 0)!
else"
! !(i, j) = LinearFibonacci(k - 1)!
" "return (i +j, i)!
• Runs in O(k) time.!
Phạm Bảo Sơn - DSA
Multiple Recursion"
• Motivating example: summation puzzles!
• pot + pan = bib !!
• dog + cat = pig !!
• boy + girl = baby !!
• Multiple recursion: makes potentially many
recursive calls (not just one or two).!
• Find all subset of a certain length.!
Phạm Bảo Sơn - DSA
!
Algorithm for Multiple
Recursion"
Algorithm PuzzleSolve(k,S,U):!
Input: An integer k, sequence S, and set U (the universe of elements to test)!
Output: An enumeration of all k-length extensions to S using elements in U!
!without repetitions!
if k = 0 then"
!Test whether S is a configuration that solves the puzzle!
"if S solves the puzzle then"
" "return “Solution found: ” S!
else !
for all e in U do"
! !Remove e from U !{e is now being used}!
! !Add e to the end of S!
" "PuzzleSolve(k - 1, S,U)!
! !Add e back to U !{e is now unused}!
! !Remove e from the end of S!
!
Phạm Bảo Sơn - DSA
Visualizing PuzzleSolve"
Initial call
PuzzleSolve( 3,(),{a,b,c})
PuzzleSolve(2,a,{b, c}) PuzzleSolve(2,b,{a, c}) PuzzleSolve(2,c,{a,b} )
PuzzleSolve(1,ab,{c} ) PuzzleSolve(1,ba,{c}) PuzzleSolve(1,ca,{b} )
abc bac cab
PuzzleSolve(1,ac,{b} ) PuzzleSolve(1,bc,{a} ) PuzzleSolve(1,cb,{a})
acb bca cba
Phạm Bảo Sơn - DSA
