Transcript If n = 1, then n!

Monday, 12/9/02, Slide #1
CS 106 Intro to CS 1
Monday, 12/9/02
QUESTIONS??
On HW #5 (Due 5 pm today)
Today:
Recursive functions
Reading: Chapter 13
Exercises: pp. 328 ff. #4, 10, 15
Wednesday:
Overview and discussion of final exam
Evaluations
Monday, 12/9/02, Slide #2
New topic: Recursion (Chap. 13)
 Recursion – means a concept or quantity whose
definition refers to itself. An algorithm is called
recursive if its implementation contains a call
to itself .
 Example:
 Factorial: n! = 1 * 2 * 3 * ... * n. Or we can give the
following recursive definition: If n = 1, then n! = 1.
If n > 1, then n! = n * (n – 1)!
Monday, 12/9/02, Slide #3
Two basic examples
 Factorial(): Design a function definition that
implements the recursive definition of Factorial().
 Fibonacci(): Design a function that produces the
sequence: 1 1 2 3 5 8 13 21, in which the first two
numbers are 1, and from then on each number is the
sum of the two previous ones, i.e., Fibonacci(1) =
Fibonacci(2) = 1, and for n > 2, Fibonacci(n) =
Fibonacci(n-1) + Fibonacci(n-2).
Monday, 12/9/02, Slide #4
Criteria for (Good) Recursive
Functions
 Recursive Case: A recursive
function must contain at least
one statement in which the
function calls itself.
 Base Case: There must also be
at least one case in which the
function does not call itself.
 Reaching the base: Each
recursive call must result in a
case that is "closer to" the base
case, and the sequence of calls
begun by any recursive call
must eventually reach the base
case.
int Fib (int n)
{
if (n <= 2)
{
return 1;
}
else
{
return Fib (n-1) + Fib (n-2);
}
}
Monday, 12/9/02, Slide #5
Recursive algorithm
for binary search
 Binary Search Algorithm: To search for key in array A[ ],
from index bot to index top,
 If bot >= top (empty or 1-item array), check for key in 1 spot,
otherwise key has not been found.
 If bot < top (array with > 1 items)
 Compute index mid = (bot + top) / 2;
 If key == A[mid], we’re done!
 Else if key > A[mid],
do Binary Search from index mid +1 to top
 Else (key < A[mid]),
do Binary Search from index bot to mid -1