17-recursion.tex

% LaTeX source for ``Introduction to Computer Science (Java/Pi Edition)''
% Copyright (c) 2015- David S. Read, All Rights Reserved

\chapter{Recursion}

\index{recursion}


\section{Divide and conquer}

\index{divide and conquer}
\index{algorithm!divide and conquer}

One approach that we may use when faced with a large task is to break it into smaller tasks, each a subset of the original large one. We work out each smaller task and in the process end up completing the larger one.

This process of expressing an algorithm by having it apply the same logic to a subset of the data is known as \textbf{recursion}.

Here are a couple of visual depictions of recursion. 

In this first image we see traditional \textit{Russian dolls}, where a set of dolls, each essentially a larger version of the previous, nest together to form the whole.\footnote{By Photo: RK812, Doll carved by Zvezdochkin, painted by Malyutin - Sergiev Posad Museum of Toys, Russia, Public Domain, https://commons.wikimedia.org/w/index.php?curid=5051554}

\beforefig
\centerline{\includegraphics[height=2.5in]{images/recursion_First_matryoshka_museum_doll_open.jpg}}
\afterfig

In our second image, we see an artist painting a picture which shows an artist painting a smaller picture, which shows an artist painting a smaller picture...\footnote{Stack Exchange Network, http://programmers.stackexchange.com/questions/93826/how-do-i-explain-recursion-to-a-8-years-old-kid}

\beforefig
\centerline{\includegraphics[height=2.5in]{images/recursion_quora.jpg}}
\afterfig

Both of these examples may help you understand recursion, however the images seem to be repeating the same information at different sizes. When we talk about using recursion in a computer program, it is the size of the data (meaning the values or the number of elements in an list) that is changing. In other words we are working with subsets, not duplicate information.

Here is an example of using recursion in the real world.\footnote{Quora, https://www.quora.com/How-should-I-explain-recursion-to-a-4-year-old} 

\begin{quotation}
The person behind you in a movie theater asks you what row you're sitting in. You don't want to count, so you ask the person in front of you what row they are sitting in, knowing that you will respond to the person behind you one greater than the answer the person in front of you gives. The person in front will ask the person in front of them. This will keep happening until the question reaches the front row, and it is easy to respond: "I'm in row 1!" From there, the correct message (incremented by one by the person in each row) will eventually make its way back to the person who asked.
\end{quotation}

\pagebreak

This exemplifies several key aspects of using recursion:
    
\begin{enumerate}
    \item The question ("what row am I in?") needs to be rephrased recursively as: "how many people are in front of me + 1?" with a base case of zero people in front of me (the front row).
    
    \item Considering the process of each person asking the person in front of them the same question, we can see that a recursive approach will work its way down to a base case (row 1 in this example) and then ``unwind'' back through all the recursive requests to return to the original requester who now has the answer.
    
    \item At each step, the process is the same, each requester has to add one to the answer from the person in front of them.
    
\end{enumerate}    

One clarification related to the movie theater row example. The description involved multiple people, each running the same ``code'' which asked the person in front for their row number and added 1 to the answer before responding to the person behind them. However, when we use a recursive process in our program, there is only the one computer and program keeping track of all the repeating steps.

\section{Fibonacci sequence}    

Let's apply this concept in a mathematical context. One mathematical problem that is easily solved using a recursive approach is calculating Fibonacci numbers. As a refresher, the Fibonacci sequence starts out with the values 0 and 1. It then continues by adding the last two numbers of the current sequence to arrive at the next number in the sequence.

Specifically, starting with 0 and 1 as the sequence, we add them resulting in 1, which becomes the new end of the sequence. The last two numbers are now 1 and 1 which when added together are 2, which again becomes the last number in the sequence. The last two numbers are now 1 and 2 which sum to 3. This continues, 2 plus 3 is 5, 3 plus 5 is 8...

Here are the first 12 numbers in the Fibonacci sequence:

\beforeverb
\begin{verbatim}
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
\end{verbatim}

Thinking about how this is calculated, we can break the problem down into a process of adding together the last two numbers in the current sequence, which in turn adds the previous last two numbers in the sequence, and continuing on until we have as much of the sequence as desired.

To create a function that is recursive we have to be sure to answer three questions, matching the key aspects we discussed in the movie theater row calculating example:

\begin{enumerate}
	\item What is the base case and how is the function written to identify it?
		
	\item What information does the recursive function need in order to calculate the new value?
	
	\item When is the process complete so that the function knows to stop recursing?
\end{enumerate}

In the case of the Fibonacci sequence we would answer those questions as follows:

\begin{enumerate}
	\item The base case is that the first value in the sequence is 0 and the second value in the sequence is 1.

	\item The function will need to add the last two numbers currently in the sequence if the base case does not apply.

	\item The function will need to be told which element of the sequence to compute.
\end{enumerate}

Here is how we could declare our \texttt{fibonacci} function, which accounts for the argument value we need (element number in the sequence we are to calculate):

\beforeverb
\begin{verbatim}
def fibonacci(position):
\end{verbatim}
\afterverb

Next we need to write the code to apply the base case. In other words, we know that the Fibonacci value for \texttt{position} 0 is the value 0 and the Fibonacci value for \texttt{position} 1 is the value 1:

\beforeverb
\begin{verbatim}
def fibonacci(position):
    if position == 0:
        return 0
    if position == 1:
        return 1
\end{verbatim}
\afterverb

Finally we need to add the \textbf{recursive} part of the process. In this case we know that to compute the third value in the sequence we add the second and first values. For the fourth value we add the third and second values. More generally, for the \texttt{nth} value we add the \texttt{nth~-~1} and \texttt{nth~-~2} values. In code we would write the following to represent that logic:

\beforeverb
\begin{verbatim}
return fibonacci(position - 1) + fibonacci(position - 2)
\end{verbatim}
\afterverb

What this says is that to calculate the Fibonacci value at a \texttt{position} we will return the result of calling the \texttt{fibonacci} function passing \texttt{position~-~1} and adding to that the value of calling the \texttt{fibonacci} function passing the value \texttt{position~-~2}.

\pagebreak

Here is a complete version of a program implementing our recursive Fibonacci algorithm in a function called \texttt{fibonacci}. The code calls the \texttt{fibonacci} function passing the values 0 through 9 to display the first 10 values of the Fibonacci sequence\footnote{Remember sequence position 0 contains the first value.}:

\beforeverb
\begin{verbatim}
def fibonacci(position):
    if position == 0:
        return 0
    if position == 1:
        return 1

    return fibonacci(position - 1) + fibonacci(position - 2)

pos = 0
while pos < 10:
    print(fibonacci(pos), end = ',')
    pos = pos + 1
\end{verbatim}
\afterverb

The program produces the following output:

\beforeverb
\begin{verbatim}
$ python fibonacci.py 
0,1,1,2,3,5,8,13,21,34,
\end{verbatim}
\afterverb

It may take some time studying and thinking through what is happening when the \texttt{fibonacci} function runs and calls itself to really grasp how this approach works.

One way to picture the code running is to imagine a stack of plates such as you might see at a salad bar. As new plates are added, the ones already there are pushed down. We call this a \textbf{Last-in, First-out} stack. The last plate added will be the first one removed. When we write recursive functions we are creating such a stack of values in the computer.

\index{stack}

When a function calls itself, the current set of parameters and local variables are "pushed down" and temporarily replaced by a new set of parameters and local variables which the recursive call uses. Once the recursive call ends, those original values are "popped up" and put back for the original function call to continue using.

Fundamentally, each call to a function creates its own unique set of parameters and local variables which are separate from the parameters and local variables used by any other calls to the same function. This happens for each call, so if we call a function 5 times there will be five independent sets of parameters and local variables created for that function.

Let's walk through the calculation of one value in the Fibonacci sequence using our \texttt{fibonacci} function and the concept of a stack. In this example we will look at what happens when we ask for the fifth value in the sequence, which, as we saw above, is 3.

We call the \texttt{fibonacci} function passing the number 4 as the \texttt{sequencePosition} argument.\footnote{We want the fifth value in the sequence. Remember the first value in the sequence is in the zero-eth position.} Inside the function this means that the parameter \texttt{position} has the value 4. Looking at the logic in the \texttt{fibonacci} function, the two Boolean tests will be false (4 isn't 0 and it isn't 1) and we'll end up at the recursive statement:

\beforeverb
\begin{verbatim}
return fibonacci(position - 1) + fibonacci(position - 2);
\end{verbatim}
\afterverb

This means that we will call the \texttt{fibonacci} function passing the value 3 \mbox{(e.g. 4-1)}. This is a recursive request, the function is calling itself. The currently executing copy of the \texttt{fibonacci} function (with \texttt{position} = 4) will wait until it gets the answer back from its recursive calls.

We now start executing a new copy of \texttt{fibonacci} passing 3 as the value for \texttt{position}. Again, we skip past the two Boolean tests and end up at the recursive call. We then recurse again, passing 2 as the value for \texttt{position}. This new executing copy of the \texttt{fibonacci} function will wait until it gets the answer back from its recursive call. We now have two copies of the \texttt{fibonacci} function waiting on results from their recursive calls.

Eventually we'll end up calling \texttt{fibonacci} with the value 1, which is a base condition. In that case the function returns the number 1 back to its caller. This allows the previous executing copy of \texttt{fibonacci} to continue running, using the returned value. This process continues to unwind its way back to the top of the stack, which is the original call made to \texttt{fibonacci} when the program started running.

Thinking back to the movie row example, this is similar to how each person asking the person in front of them for their row number has to wait for that person to get an answer from the person in front of them before they will respond to the person behind them. Eventually the request reaches a person in the front row who immediately responds ``1''.

\pagebreak

Here are two depictions of the entire recursive process for our Fibonacci example where we ask for the fifth element in the sequence. The first depiction illustrates the set of recursive calls showing the \texttt{sequencePosition} value being passed into the function with each call. The numbers in the circles depict the order in which these recursive calls occur when the program runs.

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-fibonacci-depiction-0.eps}}
\afterfig

This next image depicts the value being returned by each call and the order in which those returns occur. You'll note that the initial call (where we pass in the argument 4 asking for number in the fifth position of the sequence) contains the number 3, which is the fifth number in the sequence. That is calculated based on the summing of the values from the recursive calls right below, which use the sums of values from the recursive calls below them.

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-fibonacci-depiction-1.eps}}
\afterfig

\section{Searching an ordered list}

Another example of a common recursive process is searching an ordered list for a specific value. For example, imagine we are creating a program to check the spelling of words. We already have an list of words that is stored in alphabetical order. Our program needs to accept a word from the user and tell him or her whether it is spelled correctly, or at least if it is a word that is in our list of words.

One way we could write the search would be to start at the beginning of the list and hunt through until we either find a match or arrive at the end of the list. If we find a match we can stop searching and tell the user that the word is spelled correctly. If we reach the end of the list we know the word isn't in our list and we tell the user we can't find that word.

This is a fairly inefficient approach to searching the list. If there are 1,000,000 (one million) words in the list, we will have to hunt through all million words in order to determine that a word is misspelled. If we wanted to use this to spell check a term paper, it would take a long time to run. Is there a better way?

Consider how you would do this task manually, perhaps using a dictionary. You would not start reading words at the beginning and go sequentially through until you matched the word or got to the end of the dictionary. Instead, what would you do? You would jump to the section of the dictionary that begins with the same letter that the word begins with. You would then jump several pages forward, check if the word was further on or earlier and jump forward or back in smaller and smaller increments as appropriate.

With this approach when are you done? Just like the earlier sequential approach, if you find a match you are done and you know the word is spelled correctly. What about the case where the word isn't in the dictionary? You know you are done when you find the location where the word would be if it were there. In other words, when you find two words next to each other where the first comes before the word you seek and the second comes after, you know that your word isn't present.

\section{Binary search}

To search this way using our ordered list example with a computer program we have to make one simplification to the process just described. As humans looking at a dictionary, which is generally organized to make jumping to a specific first letter easy, we can get to the correct part of the dictionary very fast. Our list, however, doesn't have a way to know where each set of words beginning with a specific letter starts. Instead we'll have the computer jump to the middle of the list and check for which of three conditions is true:

\begin{enumerate}
	\item The word in the middle of the list matches the word we are searching for
	\item The word in the middle of the list comes before (in alphabetical order) the word we are searching for
	\item The word in the middle of the list comes after the word we are searching for
\end{enumerate}

If the word is a match, we are done. We found the word and can return a result indicating the word is spelled correctly.

What about the other two cases? Based on our comparison with the word in the middle of the list we know whether the word we are searching for comes before or after the word at that location in the list.

We then logically divide the list into two parts, the set of words in the first half of the list and the set of words in the second half of the list. What we are creating are two \textbf{sublists}, each containing half of the words that were in the original list. 

If the word we seek comes after the word we found in the middle of the original list then we know that our word, if it is present in the list at all, would have to be in the second sublist (remember the list is alphabetically ordered). In this case we do not need to look at the first sublist at all, our word can't be there.

We then treat that sublist as our list to be searched and repeat the process. We jump to the middle of that sublist and check to see which of the three conditions (listed above) are met.

In terms of set size, after our first comparison we have divided the number of words to be searched in half. After the second comparison we have reduced it to one-quarter. The third comparison reduces the amount of the list remaining to one-eighth of the original. You may notice a pattern here. With each comparison we are reducing the remaining amount of the list to search by a factor of 2 of what it was previously.

It turns out this approach of searching is amazingly efficient. In fact, to search our 1,000,000 words, the worst case number of comparisons is the square root of 1,000,000. That turns out to be 1,000. Remember though, the key to being able to do this is to have the list elements in ascending order. The name of this form of search is known as a \textbf{binary search}.

\index{binary search}

We use the term \textit{binary} for the search because it continually divides the remainder of the set in half, creating two sublists. One sublist may hold a matching value and the other can be ignored.

How does this relate to recursion? Reviewing the process of a \textit{binary search} you'll note that it is carrying out the same operation on smaller subsets of the data. The operation always jumps to the middle of the remaining sublist, checks whether the value matches the one we seek or, if it doesn't match, figures out if the value would be earlier or later in the sublist.

The stop conditions are reached when either:

\begin{enumerate}
	\item A match is found
	\item The subdividing of the list has reduced down to a subset with one element and that element's value does not match the word we are seeking
\end{enumerate}

For this example, the information a recursive function would need includes the sorted list of words, the current start and end positions of the sublist being searched and the word being sought.

The function would check the center of the sublist for the word. If the function finds a match it is done and returns a success result, either a Boolean \texttt{true} or perhaps the list index location containing the word. 

If the word is not matched at the center of the sublist, the function will check whether the word is alphabetically greater or less than the word found in the middle of the list. It then makes a recursive call, replacing the beginning or ending value of the sublist with the location of the old center, offset by one. For example, if the word being sought is greater than the one found then the recursive call needs to check the elements from the old center plus one to the end of the sublist.

\section{Depicting a successful binary search}

Let's illustrate the process of a binary search without worrying about programming it yet. First, we'll work through a depiction of the process where the value we are searching for is in the list. 

For our example, we start with an list containing 10 fruit names in alphabetical order. In the image we see each word and to the left the element number in the list which contains that value. The list has 10 values so the list elements are numbered 0 to 9.

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-binsearch-initiallist.eps}}
\afterfig

We want to see if the word \textbf{jujube} matches one of our words. We start by finding the middle of the list. To find the middle we add the starting index value to the ending index value and divide by 2. For this process we always use integer division (no fractional part). Given our 10 element list we calculate \texttt{(0 + 9) / 2} resulting in the integer value \texttt{4}. We compare our search term, \textbf{jujube}, to the word located in element 4, which is \textbf{elderberry}.

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-binsearch-success-1.eps}}
\afterfig

The words do not match, so we check to see if \textbf{jujube} comes before or after \textbf{elderberry}. It comes after, meaning that if it is in the list it must be in an element further down the list. All the elements before the one containing \textbf{elderberry}, as well as the element containing \textbf{elderberry}, cannot contain our word and do not need to be looked at.

Since we know the word would come after the position just checked, we change the starting position to be one greater than the position just checked, which is the value  5.

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-binsearch-success-2.eps}}
\afterfig

Now we need to repeat this process on the remaining sublist. We calculate the middle element of the remaining elements. Our updated starting element number (as described above) is 5 (one past elderberry) and the end is still 9. Our calculation is then \texttt{(5 + 9) / 2} which results in \texttt{7}. We compare our search term, \textbf{jujube}, to the word located in element 7, which is \textbf{honeydew}.

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-binsearch-success-3.eps}}
\afterfig

The words do not match, so we check to see if \textbf{jujube} comes before or after \textbf{honeydew}. It comes after, meaning that if it is in the list it must be in an element further down the list. All the elements before the one containing \textbf{honeydew}, as well as the element containing \textbf{honeydew} cannot contain our word and do not need to be looked at.

Since we know the word would come after the position just checked, we again change the starting position to be one greater than the position just checked, which is the value  8.

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-binsearch-success-4.eps}}
\afterfig

Again we repeat this process on the remaining sublist. We calculate the middle element of the remaining elements. Our new starting element number is 8 and the end is still 9. Our calculation is then \texttt{(8 + 9) / 2} which results in \texttt{8}. We compare our search term, \textbf{jujube}, to the word located in element 8, which is \textbf{jujube}.

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-binsearch-success-5.eps}}
\afterfig

The words match! The search is completed having made only 3 comparisons in our list of 10 elements.

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-binsearch-success-6.eps}}
\afterfig

\section{Depicting an unsuccessful binary search}

Here is a depiction of the binary search process where the value we are searching for is \textit{not} in the list. We start with the same list of 10 fruit names in alphabetical order. 

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-binsearch-initiallist.eps}}
\afterfig

We want to see if the word \textbf{celery} matches one of our words. As before, we start by finding the middle of the list, element 4. We compare our search term, \textbf{celery}, to the word located in element 4, which is \textbf{elderberry}.

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-binsearch-failure-1.eps}}
\afterfig

The words do not match, so we check to see if \textbf{celery} comes before or after \textbf{elderberry}. It comes before, meaning that if it is in the list it must be in an element earlier in the list. All the elements after the one containing \textbf{elderberry}, as well as the element containing \textbf{elderberry}, cannot contain our word and do not need to be looked at.

Since we know the word would come before the position just checked, we change the ending position to be one less than the position just checked, which is the value 3.

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-binsearch-failure-2.eps}}
\afterfig

Again, we need to repeat this process on the remaining sublist. We calculate the middle element of the remaining elements. Our updated ending element number (as descrbied above) is 3 (one before elderberry) and the beginning is still 0. Our calculation is then \texttt{(0 + 3) / 2} which results in \texttt{1}. We compare our search term, \textbf{celery}, to the word located in element 1, which is \textbf{banana}.

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-binsearch-failure-3.eps}}
\afterfig

The words do not match, so we check to see if \textbf{celery} comes before or after \textbf{banana}. It comes after, meaning that if it is in the list it must be in an element further down the list. All the elements before the one containing \textbf{banana}, as well as the element containing \textbf{banana} cannot contain our word and do not need to be looked at.

Since we know the word would come after the position just checked, we change the starting position to be one greater than the position just checked, which is the value 2.

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-binsearch-failure-4.eps}}
\afterfig

As usual, we repeat the process on the remaining sublist. We calculate the middle element of the remaining elements. Our updated starting element number is 2 and the end is still 3. Our calculation is then \texttt{(2 + 3) / 2} which results in \texttt{2}. We compare our search term, \textbf{celery}, to the word located in element 2, which is \textbf{cherry}.

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-binsearch-failure-5.eps}}
\afterfig

The words do not match, so we check to see if \textbf{celery} comes before or after \textbf{cherry}. It comes before, meaning that if it is in the list it must be in an element earlier in the list. 

Since we know the word would come before the position just checked, we change the ending position to be one less than the position just checked, which is the value 1. 

\beforefig
\centerline{\includegraphics[height=2in]{figs2/recursion-binsearch-failure-6.eps}}
\afterfig

We now find that the starting element position is 2 and the ending element position 1. Since start is greater than end we know the word can't be in the list. 

Fundamentally, \textbf{\textit{all the earlier elements and all the later elements have been ruled out}}. Therefore the word must not be in the list. We have completed the search having made only 3 comparisons in our list of 10 elements.

\section{Implementing a recursive binary search}

Let's look at the code to implement the binary search process we just described. We'll create a recursive function called \texttt{binary\_search} to implement the logic.

\index{recursive function}

There are four pieces of information the function needs:

\begin{enumerate}
	\item The ordered list of words
	\item The word we are searching for
	\item The current starting list element number
	\item The current ending list element number
\end{enumerate}

In the binary search process we will first calculate the center element. We will also need a variable to house the result of comparing the word being sought to the word in the center element of the sublist.

Next we need to compare the words (strings). Remember from our discussion of strings that we can compare strings using the relational operators.

The next part of the function will need to evaluate the result of the comparison.

\begin{enumerate}
	\item If we have found a match we'll return the list index position of the element containing the word. 
	\item If the search term is less than the value in the list element we will update the ending list element number to be one less than the current center position (e.g. we know the word has to be earlier in the list).
	\item If the search term is greater than the value in the list element we will update the starting list element number to be one more than the current center position (e.g. we know the word has to be later in the list).
\end{enumerate}

Finally we need to determine whether we have reached the end of the process, meaning there is no smaller subset of the original list left to search. The easiest way to figure that out is to compare the updated start and end positions. If they cross, meaning that the start position becomes greater than the end position, we have finished the search and not found a match. If the start position is equal to or less than the end position we need to recurse and check the new sublist.

Here is the entire function, which implements the process just described. Make sure that each part makes sense and that you can see how the code relates to the explanation above.

\beforeverb
\begin{verbatim}
# Conduct a binary search
# Two base cases:
#    1. Match found
#    2. No match found
def binary_search(wordlist, searchterm, startpos, endpos):
    checkpos = (startpos + endpos) // 2
    if searchterm == wordlist[checkpos]:
        # Words match - return the matching position
        return checkpos
    elif searchterm < wordlist[checkpos]:
        # search term comes earlier in list
        # change ending position
        endpos = checkpos - 1
    else:
        # search term comes later in the list
        # change starting position
        startpos = checkpos + 1

    # See if there are still more words to check
    if startpos <= endpos:
        # Still more words to check, make recursive call
        return binary_search(wordlist, searchterm, startpos, endpos)
    else:
        # No more words to check, the word is not in the list
        return -1

fruits = [ 'apple', 'banana', 'cherry', 'date', 'elderberry',
    'fig', 'grape', 'honeydew', 'jujube', 'kiwi' ]
position = binary_search(fruits, 'jujube', 0, len(fruits) - 1)
print('Found jujube?', position)
    
print('===============================')

position = binary_search(fruits, 'carrot', 0, len(fruits) - 1)
print('Found carrot?', position)
\end{verbatim}
\afterverb

When we run this we see the following output:

\beforeverb
\begin{verbatim}
Found jujube? 8
===============================
Found carrot? -1
\end{verbatim}
\afterverb

This means that \textit{jujube} was found in element 8 of the \texttt{fruits} list and \textit{carrot} was not found in the list (we chose to use -1 as the signal for not finding a match).

Let's add a few print statements so that we can see what is happening when the \texttt{binary\_search} function runs. Here is an updated version that includes some \texttt{print} output to display the variable values as the recursive calls are made. 


\beforeverb
\begin{verbatim}
# Conduct a binary search
# Two base cases:
#    1. Match found
#    2. No match found
def binary_search(wordlist, searchterm, startpos, endpos):
    checkpos = (startpos + endpos) // 2

    print('binary_search called for searchterm:' + searchterm +  
        ' startpos:' + str(startpos) + ' endpos:' + str(endpos))
    print('checkpos:' + str(checkpos) + ' word at list element:' + 
        wordlist[checkpos] + '\n')

    if searchterm == wordlist[checkpos]:
        # Words match - return the matching position
        return checkpos
    elif searchterm < wordlist[checkpos]:
        # search term comes earlier in list
        # change ending position
        endpos = checkpos - 1
    else:
        # search term comes later in the list
        # change starting position
        startpos = checkpos + 1

    # See if there are still more words to check
    if startpos <= endpos:
        # Still more words to check, make recursive call
        return binary_search(wordlist, searchterm, startpos, endpos)
    else:
        # No more words to check, the word is not in the list
        return -1

fruits = [ 'apple', 'banana', 'cherry', 'date', 'elderberry',
    'fig', 'grape', 'honeydew', 'jujube', 'kiwi' ]
position = binary_search(fruits, 'jujube', 0, len(fruits) - 1)
print('Found jujube?', position)
    
print('===============================')

position = binary_search(fruits, 'carrot', 0, len(fruits) - 1)
print('Found carrot?', position)
\end{verbatim}
\afterverb

When we run this we see some details about how the recursive calls are operating:

\beforeverb
\begin{verbatim}
$ python binary_search_addloutput.py 
binary_search called for searchterm:jujube startpos:0 endpos:9
checkpos:4 word at list element:elderberry

binary_search called for searchterm:jujube startpos:5 endpos:9
checkpos:7 word at list element:honeydew

binary_search called for searchterm:jujube startpos:8 endpos:9
checkpos:8 word at list element:jujube

Found jujube? 8
===============================
binary_search called for searchterm:carrot startpos:0 endpos:9
checkpos:4 word at list element:elderberry

binary_search called for searchterm:carrot startpos:0 endpos:3
checkpos:1 word at list element:banana

binary_search called for searchterm:carrot startpos:2 endpos:3
checkpos:2 word at list element:cherry

Found carrot? -1
\end{verbatim}
\afterverb

Make sure to study the output and trace through the recursive function calls that are executed in these examples. Drawing a table of values and keeping track of the \textit{stack} of parameter and local variable values may be helpful as well.


\iffalse

\section{Tower of Hanoi}

A classic mathematical puzzle which requires this type of problem solving is known as the \textbf{Tower of Hanoi}.\footnote{https://en.wikipedia.org/wiki/Tower\textunderscore of\textunderscore Hanoi}

The puzzle is comprised of a base with three vertical posts and a set of disks with different diameters. The disks have a hole in the center so that they may be stacked on the vertical posts. The initial setup requires the player to stack, in order from largest (on the bottom) to smallest (on the top), all of the disks on one of the posts. 

The objective of the game is to move the disks and recreate the ordered stack on a different post. The rules are simple:

\begin{enumerate}
	\item Only one disk may be moved at a time
	\item A move consists of picking up one disk and moving it to another post. The disk must be the top most disk on one of the posts
	\item A larger diameter disk may never be placed on a smaller diameter disk
\end{enumerate}

It turns out that an effective strategy for solving this puzzle is to break the problem down into smaller steps. Instead of worrying about all the disks we can concentrate on the first two. We can move them onto the two empty posts. We can then move the smaller of the two on top of the larger of the two. We can then move the third disks to the empty post, put the smallest disk back on the original post and the second-smallest disk on the  
subset 

\fi

\section{Glossary}

\begin{description}

\item[recurse:] Having a function call itself, typically with a subset of the data that was provided to the initial function call. 
\index{recurse}

\item[recursion:] The use of a function that uses its own definition to apply the same logic over and over. Typically this is used to break a large problem into smaller pieces and ultimately solve the larger problem by combining the results of the recursive calls.
\index{recursion}

\item[recursive function:] A function that uses recursion.
\index{recursive function}

\item[stack:] A data structure where information (data) is placed in an ordered list. In the case of recursion, the stack holds the data from earlier calls to a recursive function that are waiting on results from their recursive calls. As recursive calls end, the previous data is retrieved from the stack and restored for the earlier function call to use.
\index{stack}

\end{description}

\newpage

\section{Exercises}

\begin{ex}
Write a program that takes an ordered list of integers and uses a binary search to find a specific number. Assume the numbers are all positive allowing you to use -1 as the signal for not finding a match. You should be able to use the example WordSearch class from the chapter as a starting point for this program.
\end{ex}

\begin{ex}
Write a program that prompts the user for a positive number and then sums all the numbers from 1 up to the entered value. The program \textbf{may \textit{not} use a loop}. Rather, it must use a recursive function to carry out the summing process.
Here is an example of what a run of the program would look like:

\beforeverb
\begin{verbatim}
Enter a positive number: 5
Result: 15
\end{verbatim}
\afterverb

\end{ex}


\begin{ex}
Sometimes when programmers get bored or want to have a bit of fun,
they add a harmless {\bf Easter Egg}\footnote{\url{en.wikipedia.org/wiki/Easter_egg_(media)}} to their program. Modify the program from the previous exercise so that it prints a funny
message when the user types a specific value. For example you might have the program print the message \texttt{ Answer to the Ultimate Question of Life, the Universe, and Everything} when the user enters the number 42. 
The program should behave normally for all other supplied values.  Here are a couple of sample executions of the program:

\beforeverb
\begin{verbatim}
Enter a positive number: 42
Answer to the Ultimate Question of Life, the Universe, and Everything
Result: 903

Enter a positive number: 7
Result: 28
\end{verbatim}
\afterverb
%
We are not encouraging you to put Easter Eggs in your 
programs---this is just an exercise.

\end{ex}