Data Structures and Algorithms
Chapter 5
Recursion
• A recursive function is a function which is defined in terms of itself.
• A recursion, in programming, is a way of implementing repeated execution of statements (or a method), where a method invokes itself.
• Example: Factorial
n! =1 ifn=0 n * (n – 1)! if n ≥ 1
• Java implementation
1 2 3
public static int factorial(int n) throws IllegalArgumentException { if(n<0)
4
5
6
7 8}
else if (n == 0) return 1;
// base case
// recursive case
Recursion Factorial
throw new IllegalArgumentException( ); // argument must be // nonnegative
else
return n * factorial(n-1);
• Recursion trace
Recursion Factorial
• Recursive calls
Recursion Factorial
• Returning from calls
Recursion Factorial
Recursion Factorial
• Running time of factorial: O(n)
– One execution of the method takes O(1) – It is invoked n – 1 times => O(n)
– O(1) x O(n) = O(n)
Recursion Binary Search
• Search a sequence of n elements for a target element.
• Linear search
– Examine each element while scanning the sequence – Best case: one comparison, or O(1)
– Worst case: n comparisons, or O(n)
– On average: n/2 comparisons, or O(n)
• Binary search
– If the sequence is sorted, we can use binary search – Running time is O(log n)
low
mid
high
Recursion Binary Search
Search 17
0 1 2 3 4 5 6 7 8 9 10 2 3 5 7 11 13 17 19 23 29 32
compare 17 with
0 1 2 3 4 5 6 7 8 9 10
11 12 13 14 41 45 54 66
2 3 5 7 11 13 17 19 23 29 32 low mid high
compare 17 with
0 1 2 3 4 5 6 7 8 9 10
11 12 13 14 41 45 54 66
2 3 5 7 11 13 17 19 23 29 32 low mid high
0 1 2 3 4 5 6 7 8 9 10 2 3 5 7 11 13 17 19 23 29 32
11 12 13 14 41 45 54 66
low = mid = high
compare 17 with
11 12 13 14 41 45 54 66
Recursion Binary Search
• Pseudocode
Algorithm binarySearch(int[ ] data, int target, int low, int high)
If low > high // target is not found return false
else
mid = floor((low + high)/2) // median candidate if target = data[mid] // target found
return true
else if target < data[mid]
search data[low .. mid-1] recursively else
search data[mid+1 .. high] recursively
• Java implementation
1
public static boolean binarySearch(int[ ] data, int target, int low, int high) {
2
3
4
5
6
7
8
9
10
11
12 } 13 }
Recursion Binary Search
if (low > high)
return false; // interval empty; no match
else{ intmid=(low+high)/2; if (target == data[mid])
return true; // found a match
else if (target < data[mid]) // recurse left of the middle
return binarySearch(data, target, low, mid - 1); else // recurse right of the middle
return binarySearch(data, target, mid + 1, high);
• Running time analysis
– Execution of one call takes O(1).
Recursion Binary Search
– Each time binary search is (recursively) invoked, the number of elements to be searched is reduced to at most half.
– Initially, there are n elements.
– In the first recursive call, there are at most n/2
elements.
– In the second recursive call, there are at most n/4 elements.
– andsoon...
• Running time analysis (continued)
Recursion Binary Search
– In the j-th recursive call, there are at most n / (2j) elements.
– In the worst case, the target is not in the sequence. In this case, recursion stops when there is no more elements to be searched.
– The max. number of recursive calls is the smallest
integer r such that
nr 1 2
– Or, r is the smallest integer such that r > log n
– Therefore, r logn 1
– So, the total running time is O(log n)
Recursion More Examples
• Print array elements recursively – Pseudocode
Algorithm printArrayRecursively(data, i) if i = n, return
else
print data[i] i=i+1
printArrayRecursively(data, i)
1
2
3
4
5
6 7} 8}
return; else{
Recursion More Examples
• Print array elements recursively – Java code
public static void printArrayRecursive(int[ ] data, int i){ if (i == data.length)
System.out.print(data[i++] + ” “); printArrayRecursive(data, i);
Recursion More Examples
• Reversesequencerecursively–Pseudocode
Algorithm reverseArray(data, low, high) if low >= high, return
else
swap data[low] with data[high] reverseArray(data, low+1, high-1)
1
public static void reverseArray(int[ ] data, int low, int high) {
2
3
4
5
6 7} 8}
Recursion More Examples
• Reversesequencerecursively–Javacode
if (low < high) {
int temp = data[low];
data[low] = data[high];
data[high] = temp; reverseArray(data, low + 1, high - 1);
• Binarysum–Javacode
1 2 3 4 5 6 7 8
public static int binarySum(int[ ] data, int low, int high) { if (low > high) // zero elements in subarray
9} 10 }
return data[low]; else{
Recursion More Examples
return 0;
else if (low == high) // one element in subarray
int mid = (low + high) / 2;
return binarySum(data, low, mid) +
binarySum(data, mid+1, high);
• Definition: power(x, n) = xn
• Recursive definition
1
2
3
4
5 6}
if(n==0) return 1;
• Execution of each method call takes O(1).
Recursion Computing Powers
power(x,n)= 1 ifn=0
x * power(x, n-1) otherwise
• Direct implementation
public static double power(double x, int n) {
else
return x * power(x, n-1);
• The method is invoked (n + 1) times.
• Running time is O(n)
• There is an efficient method. • Let kn
2 n
• Ifniseven,k2 andifnisodd,
k n 1 2
• So,
n 2
k2 2 n
if n is even if n is odd
xx x
n12
k 2 2 n1
xx x
Recursion Computing Powers
Recursion Computing Powers
• Then, we can redefine power(x, n) as follows:
power(x, n) =
1
if n = 0
if n is even
n2 powerx,2
n2
if n is odd
powerx,2 x
• Implementation
1
2
3
4
5
6
7
8
9
10 11 }
return 1; else{
Recursion Computing Powers
public static double power(double x, int n) { if(n==0)
double partial = power(x, n/2); // use integer division of n double result = partial * partial;
if(n%2==1) //ifnodd,includeextrafactorofx
result *= x; return result;
} • Execution of one call takes O(1).
• The method is invoked O(log n) times.
• Running time is O(log n)
• Illustration
Recursion Computing Powers
Recursion Designing Recursive Algorithms
• Two components: base case and recursion
• Base case:
– Recursive call stops when a certain condition is met.
– This is usually referred to as base case.
• Recursion: When the condition of the base case is not
met, the algorithm invokes itself recursively.
• When poorly designed, very inefficient.
• Make sure the base case is always reached to avoid infinite recursion.
Recursion Parameterizing Recursion
• Design of recursive algorithms sometimes requires the change of signature by adding more parameters.
• Natural signature of binary search: binarySearch (data, target)
• Recursive design requires additional parameters: binarySearch(data, target, low, high)
• Cleaner public interface:
public static boolean binarySearch(int[ ] data, int target) {
return binarySearch(data, target, 0, data.length – 1); }
• Requires more memory.
Recursion Tail Recursion
• Recursion allows exploitation of repetitive structure of a problem.
• Makes algorithm description more readable; avoids complex analyses and nested loops.
• Tail recursion: A recursive call is the last operation.
• A tail recursion can be converted to a non-recursive algorithm (or implementation) that does not use additional memory.
• Example: binary search
Recursion Towers of Hanoi (Exercise)
• Well known problem
• Given3pegsa,b,andc
• Peg a has n disks, the smallest on the top and the largest at the bottom
• Move all disks from a to b
• Use c as a temporary peg
• Initial
• Final
Recursion Towers of Hanoi (Exercise)
abc
abc
Recursion Towers of Hanoi (Exercise)
• When moving disks:
– One disk at a time
– Never place a larger disk on top of a smaller disk
• Each disk has a label
– Label of the smallest disk is 1
– Label of the next smallest disk is 2 –…
– Label of the largest disk is n
References
• M.T. Goodrich, R. Tamassia, and M.H. Goldwasser, “Data Structures and Algorithms in Java,” Sixth Edition, Wiley, 2014.