Recursion
CS221N, Data Structures
1
Final Exam
In case anyone’s making travel plans now…
Wednesday, December 10
12 noon – 3 PM
Location: TBA
2
Recursion
Definition
A programming technique where a function calls itself
Very effective technique in programming
Used to solve a wide class of problems
Triangular numbers (3)
Factorials (12)
Fibonacci (14)
Anagrams (15)
Binary Search (21)
Towers of Hanoi (28)
3 Mergesort
Example: Triangular Numbers
1, 3, 6, 10, 15, 21, 28, …
Start with 1, get the next number by adding 2, get the
next by adding 3, the next by adding 4, etc.
Used to count the number of squares in a triangle:
Forms an infinite set
4
Key with Recursion
Separate the problem into:
A base case which you know to be true
A recursive step, which represents the answer to a larger problem in terms of a
smaller one
Idea, the recursive step will get you closer to the base case.
Let’s solve triangle(n) in this way, where n is the row of the triangle:
triangle(1) = 1
triangle(2) = 3
triangle(3) = 6
triangle(4) = 10
5
Triangular Numbers and Recursion
Note:
triangle(1) = 1
triangle(2) = 3
triangle(3) = 6
triangle(4) = 10
We can note that, in general:
triangle(n) = n + triangle(n-1)
This can be our recursive step
Which will carry us to the base case:
triangle(1) = 1
This cannot be broken down any further
6
Triangular Numbers and Recursion
Here’s our recursive solution:
triangle(1) = 1, triangle(n) = n + triangle(n-1)
In Java:
public int triangle(int n) {
if (n == 1) return 1;
else return n + triangle(n-1);
}
7
Scope
In Java, each function
call creates a new
‘scope’
Each of which declares
a new version of n,
which is visible
Suppose we call
triangle(5)
public int triangle(int n) {
if (n == 1) return 1;
else return n + triangle(n-1);
}
8
Recursive Methods
Characteristics:
They call themselves
When they call themselves, they do so to solve a smaller problem
A base case must exist
What happens if it doesn’t?
Therefore, the recursion must be able to stop at some point
As it did with triangle, at n=1
triangle(1) = 1
9
Iteration
Anything recursive can be made iterative, using a while or for loop:
int triangle(int n) {
int total = 0;
while (n > 0) {
total += n;
n--;
}
}
10
Efficiency of Recursion
Recursion is very often simpler and easier to read
But, often is slower. Why?
Overhead of function calls
Sometimes, you can make redundant recursive calls
We’ll see an example of this with Fibonacci
Also often uses more memory. Why?
When we call triangle(1), we’re storing data from the outer recursive calls
So the main merit is simplicity.
11
Mathematical Induction
This can be a convenient way to represent a recursive problem:
tri(n) = { 1 n=1
{ n*tri(n-1) n>1
12
Example: Factorials
Let’s start by representing fact(n) by mathematical induction:
And, now let’s write the Java function:
13
Factorial Scope
In Java, each function
call creates a new
‘scope’
Each of which declares
a new version of n,
which is visible
Suppose we call
factorial(4)
public int factorial(int n) {
if (n == 0) return 1;
else return n * factorial(n-1);
}
14
Fibonacci Numbers
Mathematical Induction:
fib(n) = {1 n=0
{1 n=1
{fib(n-1) + fib(n-2) n>1
Produces the sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34….
Would recursion or iteration be better here? Let’s think.
Develop Java function
Draw tree of recursive calls
What’s bad?
15
Recall Binary Search: Idea
Only uses ordered arrays
Check the middle element
If it’s too low, restrict search to the first half of the array
Otherwise restrict search to the second half of the array
And repeat.
16
Binary Search
Array has values 1-100
First search: Check element 50
50 > 33, so repeat on first half (1-49)
Second search: Check element 25
25 < 33, so repeat on second half (26-49)
Third search: Check element 37
37 > 33, so repeat on first half (26-36)
Fourth search: Check element 31
31 < 33, so repeat on second half (32-36)
Fifth search: Check element 34
34 > 33, so repeat on first half (32-33)
Sixth search: Check element 32
32 < 33, so repeat on second half (33)
Seventh search: Check element 33! Found.
17 So 7 comparisons. With linear search, it would’ve been 33.
Our implementation before was iterative…
public int find(long key) {
int lower = 0;
int upper = nElems-1;
int curIn;
while (true) {
curIn = (lower + upper) / 2;
if (a[curIn] == key) return curIn;
else if (lower > upper) return -1;
else {
if (a[curIn] < key) lower = curIn + 1;
else upper = curIn – 1;
}
}
18 }
But we can also do it recursively!
If we think of binary search in these terms:
Start lower at 0, and upper at n-1
Let mid = arr[lower+upper]/2
If arr[mid] = key, return mid # we’re done
else if lower > upper, return -1 # not found
else if arr[mid] > key:
perform binarysearch on arr[lower…mid-1]
else if arr[mid] < key:
perform binarysearch on arr[mid+1…upper]
So we have TWO base cases. One if the element is found, and the other if
19 it is not found.
Using this pseudocode, let’s do it in Java…
Start lower at 0, and upper at n-1
Let mid = arr[lower+upper]/2
If arr[mid] = key, return mid # we’re done
else if lower > upper, return -1 # not found
else if arr[mid] > key:
perform binarysearch on arr[lower…mid-1]
else if arr[mid] < key:
perform binarysearch on arr[mid+1…upper]
20 Each call: need key, lower and upper indices
Complexity… say n = 2^i
We can prove complexity of a recursive function…
Note, every call to binarysearch had some number of comparisons and
assignments, call it c
So the first call, we perform on an n-element array:
c operations
The second call, we perform on an (n/2)-element array:
c operations
The third call, we perform on an (n/4)-element array:
c operations
….
The (i+1)th call, we perform on an (n/n) element array:
21
c operations
Operation Count
If n=2i, we have (i+1)*c operations
But i = log2n!
So the total number of operations is: (log2n + 1)*c
Which is O(log2n)! So it’s the same complexity as iteration
Doesn’t mean it runs at the same speed!
Just means the runtime scales in the same way with the input.
22
Anagrams
Involves producing all possible combinations of the letters of a word.
Example: Anagram the word cat:
cat
cta
atc
act
tca
tac
Six possible combinations
23
Anagrams: General
In general, for a word of n letters, there will be n! combinations assuming
all letters are distinct
We saw for cat (3 letters), there were 6 possible
If some letter(s) repeat themselves, this will reduce the number of
combinations. Example, tat only has 3:
tat
att
tta
24
Anagram Algorithm
Anagram a word with n letters:
Anagram the rightmost n-1 letters
If n=2, display the word
Rotate all n letters
Repeat these steps n times
Where this is a rotation ->
Gives every letter a chance
25
to begin the word
Recursive
anagrams for
“cat”
26
rotate() and doAnagram() function
Java implementation, page 266
We will write:
A rotate() function which moves each character one slot to the left, and the
first character in the last position
A recursive anagram() function which invokes rotate().
Base case: n=1, just return
Recursive step (do n times):
anagram(n-1)
display if n=2
rotate(n)
27
Output Produced
cats cast ctsa ctas csat csta
atsc atcs asct astc acts acst
tsca tsac tcas tcsa tasc tacs
scat scta satc sact stca stac
28
Towers of Hanoi
An ancient puzzle consisting of disks on pegs A, B and C
Start all disks on peg A
Object: Transfer all disks from A to C
Can only move one at a time
Cannot place a disk on one that’s smaller
Note: This algorithm is EXPENSIVE for large # of disks
29
Recursion
With recursion, it’s
always good to break a
problem into smaller,
easier problems
For example:
Completing the
problem requires:
Moving the top three
disks to (B)
Moving the lowermost
disk to (C)
Moving all three disks
from (B) to (C)
30
Of course..
We broke a rule, can’t
move multiple disks
But, moving top three
to (B) is a smaller
problem:
Move the top two to
(C)
Move the third to (B)
Move the other two
from (C) to (B)
31
Similar for moving top
So…
# A is source peg
# B is intermediate peg
# C is destination peg
Solving
TOH(n,A,B,C):
Solve TOH(n-
1,A,C,B)
Move nth to C
Solve TOH(n-
1,B,A,C)
32
Base Case?
For TOH(n,A,B,C):
Well if there’s just one
disk (n=1), move from
A to C!
Java implementation,
page 278
Note: It’s just a few
lines!
33
Complexity
For n disks:
(n disks) - 1st call, 2 recursive calls (n disks)
(n-1 disks) Two 2nd calls, 2 recursive calls
(n-2 disks) Four 3rd calls, 2 recursive calls
…
(1 disk) Many nth calls, base case
Let’s draw the tree
See why, this is too expensive for large numbers of disks?
Old legend: In remote India temple, monks continuously work at solving this
problem with 64 disks and 3 diamond towers
The world ends when they are finished
No worries, it will take forever anyway….
34
Number of Operations
Each recursive call generates two recursive calls, and a constant number
of operations (call it c)
First call: c
Two second calls, times c: 2*c
Four third calls, times c: 4*c
…
2n nth calls, times c: 2n*c
Complexity: O(2n) – we call this an exponential algorithm
4 disks, 16 operations
8 disks, 256 operations
35
64 disks, 1.8*1019 operations. We’re safe.
Mergesort
This begins our discussion of more advanced sorting techniques
But it uses recursion
Complexity
O(n log n)
Where the best we’ve seen so far is O(n2)
An idea of the difference:
n=10000, 100 million operations for O(n2)
n=10000, 40 thousand operations for O(n log n)
Bad thing: Memory
Requires a temporary array of size n
36
Merging
Let’s say we have an array of size n
Suppose we used recursion and solved a smaller problem (why would we
ever do that? I don’t know ) and had two sorted subarrays:
We could merge them by repeatedly comparing their first elements
37
Merge..
Have: two subarrays, and a temporary array of size n
Compare first elements
Take the lesser, and put it in the temporary array
38
Merge…
Whichever one we chose, move one spot to the right in that subarray and
repeat
39
Keep going…
40
And going…
41
And going…
42
And going…
43
Get the idea?
44
Few more…
45
Put in the rest…
When we get to the end of one subarray, just insert the rest of the other.
46
Finally…
We’re done when the temporary array is full
47
So now, we know…
If we have two sorted subarrays, we can merge them to sort the entire
array. And we can do it in O(n) time.
Just one comparison for each of the n elements
Where recursion comes in…
Say we start with n elements…
And separate into two subarrays of n/2 elements…
And separate them into four subarrays of n/4 elements…
Until we get to subarrays of one element.
Trivial to merge!
48
Pictorally
…
49
So conceptually, what must we do?
mergesort(A, n): # Sort an array of size n
mergesort(first half of A, n/2)
mergesort(second half of A, n/2)
merge(first half of A, second half of A)
50
Let’s add a merge() procedure to this class. (p.
289)
class DArray {
private long[] theArray;
private int nElems;
public Darray(int max) {
theArray = new long[max];
nElems++;
}
public void insert(long value) {
theArray[nElems] = value;
nElems++;
51 }
What merge() accepts
A workspace array of size n
The lower, middle and upper indices of theArray to merge
First half is index lower to index (middle-1)
Second half is index middle to index upper
So n=upper-lower+1
52
Now write mergesort()
Our recursive mergesort will accept:
Workspace of size n, and lower/upper indices of theArray to sort
Initial call will pass an empty workspace, 0, and nElems-1.
53
Complexity
Every call makes two recursive calls, each with n/2 copies
First call: n copies, and generates:
Two recursive calls at (n/2) copies each, which generate:
Four recursive calls at (n/4) copies each
…
n recursive calls at (n/n) copies each
To get the total number of operations, let’s draw a tree.
54
Total number of operations
n + 2(n/2) + 4(n/4) +…. + n(n/n)
= n + n + …. + n
= (log n + 1) * n
= n log n + n
O(n log n)
Best so far!!
55
