Recursion
Daniel Archambault
CS-115: Recursion
1
Previously in CS-115
1
7
2x
4
465
1 26 357
3
Gotta see the trees through the forest!
CS-115: Recursion
2
Previously in CS-115
What is a binary tree?
CS-115: Recursion
3
Previously in CS-115
What is a binary tree?
What are the attributes of a node in a binary tree?
CS-115: Recursion
3
Previously in CS-115
What is a binary tree?
What are the attributes of a node in a binary tree?
What is the difference between in order, pre order, and post order traversals?
CS-115: Recursion
3
Previously in CS-115
What is a binary tree?
What are the attributes of a node in a binary tree?
What is the difference between in order, pre order, and post order traversals?
What is a binary search tree?
CS-115: Recursion
3
Previously in CS-115
What is a binary tree?
What are the attributes of a node in a binary tree?
What is the difference between in order, pre order, and post order traversals?
What is a binary search tree?
What is so special about an in order traversal of a binary search tree?
CS-115: Recursion
3
Previously in CS-115
To understand recursion… you need to understand recursion – 1!
Recursion
CS-115: Recursion
4
Introduction
What is Recursion?
“A method for defining functions in which the function being defined is applied within its own definition.”
–Wikipedia
In many ways, it is an alternative to iterative solutions
Solutions involving loops
CS-115: Recursion
5
Introduction
Motivation
Why learn recursion?
CS-115: Recursion
6
Introduction
Motivation
Why learn recursion? Because it’s fun. 🙂
CS-115: Recursion
6
Introduction
Motivation
Why learn recursion?
Because it’s fun. 🙂
Many problems exist in computer science where:
⋆ a recursive solution is easier to implement and more efficient You have already seen some recursive algorithms!
⋆ quicksort is recursive
⋆ binary search is recursive (review today)
CS-115: Recursion
6
Introduction
Fractals
Recursion can be used to draw nice mathematical pictures
Both Serpinski Gasket and Mandelbrot Set are from Wikipedia
CS-115: Recursion
7
Introduction
Modelling Plants and Terrain
In computer graphics, plants and terrain can be modelled recursively
L-systems have a natural recursive definition
Brandy’s Fern from Wikipedia
Fractals can be used to enhance realism of terrain
SimPlanet Project’s Fractal Mars
CS-115: Recursion
8
Introduction
Haskell
Some languages don’t even have iteration!
Believe that better programming style does not involve assignment
to variables
Assignment required for loops
quicksort [] = []
quicksort (s:xs) =
quicksort [x|x <- xs,x < s] ++ [s] ++
quicksort [x|x <- xs,x >= s]
CS-115: Recursion
9
Introduction
We kinda have already seen recursion…
In our data structures, we have seen recursion a bit
A link list consists of the current link and a link to the next link
A binary tree consists of the current node and two links to its
children which are also nodes
You can also do this with function calls
CS-115: Recursion
10
Example
Phone Book Example
CS-115: Recursion
11
Example
Iterative Solution
PhoneNumber itSearch (PhoneBookEntry book[] , String name) {
for (int i = 0; i < book.length(); i++) {
if (book[i].getName ().equals (name)) return book[i].getPhoneNumber ();
} }
CS-115: Recursion
12
Example
Recursive Solution
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
13
Recursive Program Elements
Elements of a Recursive Program
Base Case
Divide Input into Parts Recursive Case Synthesis and Return
CS-115: Recursion
14
Recursive Program Elements
Base Case
Case where solution is known or easy to compute Tells recursive program where to stop
Can be several
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
15
Recursive Program Elements
Divide Input into Parts
Problem is divided into one or more smaller instances
Parts must “head towards” base case. Otherwise, infinite recursion!
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
16
Recursive Program Elements
Recursive Case
Algorithm is reapplied to the smaller instances
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end); }
CS-115: Recursion
17
Recursive Program Elements
Synthesise and Return
Synthesise solution from result(s) of recursive call(s)
In the binary search, we just return the name
In many other recursive algorithms, not always the case.
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
18
Tracing I
Tracing Binary Search
We are nearly ready to trace this code
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
19
Tracing I
Tracing Binary Search
We are nearly ready to trace this code But first... Let’s push this on the stack.
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
19
Tracing I
The Call Stack
callStack.push (Trace Binary Search)
CS-115: Recursion
20
Recursion?
Tracing I
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
return recSearch (book, name, start, middle - 1);
CS-115: Recursion
21
Recursion?
Is actually....
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
callStack.push (local variables)
int middle = (2 + 6)/2;
....
if (name.compareTo (book[middle].getName()) < 0)
return recSearch (book, name, start, middle - 1); callStack.pop ()
Tracing I
CS-115: Recursion
21
Recursion?
Is actually....
True for any function call in Java (and most languages)
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
callStack.push (local variables)
int middle = (2 + 6)/2;
....
if (name.compareTo (book[middle].getName()) < 0)
return recSearch (book, name, start, middle - 1); callStack.pop ()
Tracing I
CS-115: Recursion
21
Tracing I
Recursion?
Is actually....
True for any function call in Java (and most languages)
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
callStack.push (local variables)
int middle = (2 + 6)/2;
....
if (name.compareTo (book[middle].getName()) < 0)
return recSearch (book, name, start, middle - 1); callStack.pop ()
Can view (and usually trace) recursion with stacks.
CS-115: Recursion
21
Tracing I
The Call Stack
Lecture = callStack.peek (); callStack.pop ();
CS-115: Recursion
22
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end); }
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end); }
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end); }
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end); }
CS-115: Recursion
23
Tracing I
Trace Binary Search
Suppose we have sorted list on the board and looking for Raul
PhoneNumber recSearch (PhoneBookEntry book[], String name, int start, int end)
{
int middle = (start + end)/2;
if (book[middle].getName ().equals (name))
return book[middle].getPhoneNumber ();
if (name.compareTo (book[middle].getName()) < 0) return recSearch (book, name, start, middle - 1);
else
return recSearch (book, name, middle + 1, end);
}
CS-115: Recursion
23
Problem Session One
Problem 1
Consider the following program
int factorial (int n) {
if (n <= 1) return 1;
return n*factorial (n - 1); }
Identify the recursive program elements Trace the execution of factorial (5);
Follow along by drawing the stack
CS-115: Recursion
24