Unit 2: Recursion
Computer Science 110C
Max Luttrell, Spring 2016
problem solving
•
Divide and conquer
•
When facing a problem, we often divide the
problem up into smaller problems
*may not be legal in your jurisdiction!
•
Real world task:
•
Deliver a secure, stable, tested iPhone app with your
team of three people which allows a user to play
blackjack versus our server for real money* and
includes a leader board and a compelling gameplay
experience with best-in-class graphics and sound
effects.
recursion
•
recursion divides a problem into smaller
problems, and the smaller problems are of
exactly the same type as the original problem
•
example: look up a word in the dictionary
dictionary pseudocode
// search for a word in a dictionary using recursive binary search
if (dictionary only has one page)
scan the page for the word
else
{
open the dictionary somewhere near the middle
determine which half of the dictionary has the word
if (the word is in the first half)
search the first half of the dictionary for the word
else
search the second half of the dictionary for the word
}
•
example: look up a word in the dictionary
dictionary pseudocode
(a little more formal)
// search for a word in a dictionary using recursive binary search
search(aDictionary: Dictionary, word: string)
if (aDictionary is size one page)
scan the page for word
else
{
open aDictionary somewhere near the middle
determine which half of aDictionary has word
if (word is in first half of aDictionary)
search(first half of aDictionary, word)
else
search(second half of aDictionary, word)
}
•
search calls function search, i.e. it calls itself!
•
each recursive call passes a smaller-size dictionary to search
•
there is a guaranteed base case (dictionary is one page)
