# Discrete Math:Recursion

Discussion Questions

1. List all the steps used to search for 9 in the sequence 1,3, 4, 5, 6, 8, 9, 11 using a binary search.

2. Describe an induction process. How does induction process differ from a process of simple repetition?

3. Describe a favorite recreational activity in terms of its iterative components, such as solving a crossword or Sudoku puzzle or playing a game of chess or backgammon. Also, mention any recursive elements that occur.

4. Describe a situation in your professional or personal life when recursion, or at least the principle of recursion, played a role in accomplishing a task, such as a large chore that could be decomposed into smaller chunks that were easier to handle separately, but still had the semblance of the overall task. Did you track the completion of this task in any way to ensure that no pieces were left undone, much like an algorithm keeps placeholders to trace a way back from a recursive trajectory? If so, how did you do it? If not, why did you not?

Side Note: Here is the reason we discuss recursion for an IT degree. Recursion is the basis of searching and sorting...here is a quote from the following website (http://www.sparknotes.com/cs/recursion/examples/summary.html)

Next we'll look at how recursion can be used in searching and in sorting to increase the efficiency of these operations. Then we'll look at how recursion can be used for certain mathematical problems, such as printing a number in different bases and computing different sequences of numbers. For most of these problems, recursion presents an incredibly elegant solution that is easy to code and simple to understand.

Recursion may be difficult to understand at first, but once you do it becomes a powerful programming tool.

5. Given this recursive algorithm for computing a factorial...

procedure factorial(n: nonnegative integer)

if n = 0 then return 1

else return n *factorial(n − 1)

{output is n!}

Show all the steps used to find 5!

#### Solution Preview

Discussion Questions

1. List all the steps used to search for 9 in the sequence 1,3, 4, 5, 6, 8, 9, 11 using a binary search.

1) Binary search algorithm depends on the array being already sorted. The Linear Search did not depend on having a sorted array. The idea behind Binary Search is to split this array in half multiple times to "zero-in" on the value we are looking for. Assume we are looking for value 9 in the array.

2) Know the index of the element that value is located in. In this case, the value 9 is located in the 6th element of the array.

3) Identify the low and high indices and find the midpoint of the array. For example, the low is 0 and the high is 7 so the midpoint is mid = low + high/ 2 = 0+7/2 = 3.5

Or 4. the midpoint is 4, which has the value of 6.

4) The value 6 is not what we are looking for at the midpoint. SO we need to search the upper half of the array. We reset our low point to the point to the index of element that is one higher than the midpoint so low = mid + 1 = 5

5) Now low point to index 5 and high still points to the last index of the array.

6) Recalculate the midpoint and using integer division ( 5+ 8)/2 = 6 as the midpoint index to use. Does the element at the mid index contain our value? yes, the index value of 6 contain the search value 9. The element in our array contain the value that we are searching for.

We can look at the Java programming code to implement a Binary Search. The Binary Search is a general algorithm that can be implemented in almost any programming language.

Here is the code:

Public final static int NOT_FOUND = -1;

Public int binarySearch ( int [ ] number, int searchValue)

{

int low = 0;

high = number. Length -1,

mid = (low + high/ 2;

while ( low <= high && number [mid] != searchValue)

{

if ( number [mid] < searchValue)

{ low = mid + 1;

else

{ high = mid -1;

}

mid = ( low + high) / 2;

}

if ( low > high)

{ mid = NOT_FOUND:

}

return mid;

}

2. Describe an induction ...

#### Solution Summary

This solution provides answers to various questions involving recursion.