Transcript Recursion

Recursion
Powerful Tool
 Useful in simplifying a problem
(hides details of a problem)
 The ability of a function to call itself

A recursive call is a function call in
which the called function is the
same as the one making the call.
 We must avoid making an infinite
sequence of function calls (infinite
recursion).

Recursion: Divide and Conquer
Problem Solving Strategy




1) Divide problem (input instance) into one or
more subproblems of exactly the same type
as the original problem
2) Solve each subproblem
3) Combine solutions of subproblems to
obtain a solution for original input
NOTE: Looks like top-down design, except
subproblems are the exactly the same type as
the original problem
2
Finding a Recursive Solution

Each successive recursive call should bring you closer
to a situation in which the answer is known.

A case for which the answer is known (and can be
expressed without recursion) is called a base case.
(The answer is usually known in the smallest version of the
problem that requires the least amount of work, for example print
out a list of only 1 element.)

Each recursive algorithm must have at least one base
case, as well as the general (recursive) case
General format for
many recursive functions
if (some condition for which answer is known)
solution statement
// base case
else
recursive function call
// general case
SOME EXAMPLES . . .
Writing a recursive function to find
n! (factorial)
DISCUSSION
The function call Factorial(4) should have value
24, because it is 4 * 3 * 2 * 1 .
For a situation in which the answer is known),
the value of 0! is 1.
So our base case could be along the lines of
if ( number == 0 )
return 1;
cont.
Now for the general case . . .
The value of Factorial(n) can be written as
n * the product of the numbers from (n - 1) to 1,
that is,
n * (n - 1) * . . . * 1
or,
n *
Factorial(n - 1)
And notice that the recursive call Factorial(n - 1)
gets us “closer” to the base case of Factorial(0).
Recursive Solution
int Factorial ( int number )
// Pre: number is initialized and number >= 0.
{
if ( number == 0)
// base case
return 1 ;
else
// general case
return number + Factorial ( number - 1 );
}
Writing a recursive function to find
Nth Fibonacci number
DISCUSSION
Conceived in 13th century by Italian mathematician to
model how fast rabbits could breed
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibnat.html#Rabbits
Fibonacci series: 0, 1, 1, 2, 3, 5, 8, 13, 21, …
1st number is 0
2nd number is 1
3rd number is 2nd number + 1st number
…
nth number is the n-1st number + n-2nd number
cont.
For situation(s) in which the answer is known, the value of
1st Fibonacci number is 0 while the value of the 2nd is 1.
So our base cases are
if ( N == 1 )
return 0;
else if (N == 2)
return 1;
The general case is
The value of Nth Fibonacci number can be written as the sum of
the n-1st and n-2nd Fibonacci numbers or,
Fibonacci (N-1) + Fibonnaci (N-2)
Notice that the both recursive calls get us “closer” to the
base cases of Fibonnaci (1) or Fibonnaci (2).
Recursive Solution
int Fib ( int N )
// Pre: N is assigned and N >= 0.
{
if ( N == 1)
// base case
return 0;
else if ( N == 2)
// base case
return 1;
else
// general case
return Fib (N-1) + Fib ( N – 2 );
}
Three-Question Method of Verifying
Recursive Functions

Base-Case Question: Is there a nonrecursive way
out of the function that works?

Smaller-Caller Question: Does each recursive
function call involve a smaller case of the original
problem leading to the base case?

General-Case Question: Assuming each
recursive call works correctly, does the whole
function work correctly?
Fibonacci Example

Base cases: N=1 and N=2



when N=1, returns 0 ….correct by definition
when N=2, returns 1 …. correct by definition
Recursive calls smaller
1st passes N-1 and 2nd passes N-2 …check
 If we assume Fib(N-1) and Fib(N-2) give us correct
values of the N-1st and N-2 numbers in the series, and
the assignment statement adds them together …this
is the definition of the Nth Fibonacci number, so we
know the function works for N > 2.
 Since the function works for N=1, N=2, N>2, then it
works for N >= 1.
 Therefore the function works. (Induction Proof) 12

Another example where recursion
comes naturally

From mathematics, we know that
20 = 1

25 = 2 * 24
In general,
x0 = 1

and
and
xn = x * xn-1
for integer x, and integer n > 0.
Here we are defining xn recursively, in terms of
xn-1
// Recursive definition of power function
int Power ( int x, int n )
// Pre: n >= 0. x, n are not both zero
// Post: Function value = x raised to the power n.
{
// base case
if ( n == 0 )
return 1;
// general case
else
return ( x * Power ( x , n-1 ) ) ;
}
Of course, an alternative would have been to use looping
instead of a recursive call in the function body.
14
Recursive function to determine if value is in
array
PROTOTYPE
void DoRetrieveItem (ArrayType info, ItemType & item, bool & found, int
start, int end);
74
36
info[0]
[1]
...
Already searched
95
[start]
index
of
current
element
to
examine
75
29
47
...
[length -1]
Needs to be searched
void RetrieveItem (ArrayType info, ItemType & item, bool & end)
// Searches list for element with same key as item
// Pre: item’s key is initialized
// Post: if key of item exists in an item in the list, item will be set to that element and
found will
//
be set to true, otherwise found will be set to false
{
//initial call to recursive private member function
DoRetrieveItem (info, item, found, 0 ) ;
}
16
void DoRetrieveItem (ArrayType info, ItemType & item, bool & found, int start,
int end)
// Searches list info for value between positions start and length-1
// Pre: the sublist, list.info[start ] . . list.info[ list.length-1] contain values to be searched
// Post: if key of item exists in an item in the sublist info[start] . .. info[ list.end], item will
//
be set to that element and found will be set to true, otherwise found will be set to false
{
if (start == end )
// one base case
return false ;
else if ( info[start] == value )
// another base case
{
item = info [start];
return true ;
}
else
// general case
return DoRetrieveItem (info, item, found, start + 1, end) ;
}
17
void DoRetrieveItem (ArrayType info, ItemType & item, bool & found, int start,
int length)
//
//
Searches list for value between positions start and end
Pre: the sublist, list.info[start ] . . list.info[ list.end] contain values to be searched and is
SORTED
// Post: if key of item exists in an item in the sublist list.info[start] . .. list.info[ list.end], item will
//
be set to that element and found will be set to true, otherwise found will be set to false
{
int mid;
if (start > end)
found = false;
// base case
else
{
mid = (start + end)/2;
if (info[mid] == item )
// base case
{
item = info[mid];
found = true ;
}
else if (info[mid] < item )
// general case
DoRetrieveItem (info, item, found, start, mid-1);
else
// general case
DoRetrieveItem (info, item, found, mid+1, end);
}
18
“Why use recursion?”
The first couple of examples could have been
written without recursion, using iteration instead.
The iterative solution uses a loop, and the recursive
solution uses an if statement.
However, for certain problems the recursive
solution is the most natural solution.
In a future example, you will see a function to print a
stack in reverse. I will use both a loop and a
temporary container. It is easier to solve this
problem using recursion.