Transcript recursion

Recursion
There are two kinds of people in the
world, those who divide the world
into two kinds of people and those
who do not.
CMSC 202
1
Recursion Terminology
Types of Recursion
 direct
 indirect
 mutual
 tail
 linear
 tree
CMSC 202
2
Recursion Terminology (con’t)
 stack (LIFO)
 push, pop
 memory map
 runtime stack
 activation record
 stack overflow (stack/heap collision)
CMSC 202
3
Iterative Factorial
int factorial(int n)
// Precondition: n >= 0
{
int i, result;
result = 1;
for (i = 1; i <= n; i++) {
result = result * i;
}
return (result);
}
CMSC 202
4
Recursive Factorial
int factorial(int n)
// Precondition: n>=0
{
if (n == 0)
return (1);
return (n * factorial(n - 1) );
}
CMSC 202
5
Iterative Power
double power(double number, int exponent)
// Precondition: exponent >= 0
{
double p = 1;
for (int i = 1; i <= exponent; i++)
p = p * p;
return (p);
}
CMSC 202
6
Recursive Power
double power(double number, int exponent)
// Precondition: exponent >= 0
{
if (exponent == 0)
return (1);
return (number * power(number, exponent-1));
}
CMSC 202
7
Recursive String Reversal
void reverseString(int length, char s[])
{
if (length < 0)
return;
cout << s[length];
reverseString(length-1, s);
}
CMSC 202
8
Recursive Summing of Integers
int sumNumbers(int m, int n)
// Precondition: m <= n
{
int total;
if (m == n)
return (n);
else
total = m + sumNumbers(m+1, n);
return (total);
}
CMSC 202
9
Recursive Nonsense
#include <iostream.h>
int thing(int);
void tap(int);
void cat(int);
void dog(int, int);
void main()
{
int a, b;
a = 5;
b = thing(a);
cout << b << endl;
CMSC 202
10
Recursive Nonsense (con’t)
a = 1;
tap(a);
b = 4;
cat(b);
b = 1;
a = 5;
dog(b, a);
}
CMSC 202
11
Recursive Nonsense (con’t)
int thing(int n)
{
int x;
if (n == 2)
return(1);
else {
x = thing(n-1) + 2;
cout << x << endl;
return(x);
}
}
CMSC 202
12
Recursive Nonsense (con’t)
void tap(int n)
{
if (n != 5) {
cout << n << endl;
tap(n+1);
cout << n << endl;
}
else
cout << n << endl;
}
CMSC 202
13
Recursive Nonsense (con’t)
void cat(int x)
{
if (x == 2)
cout << x << endl;
else {
cat(x-1);
cout << x << endl;
}
}
CMSC 202
14
Recursive Nonsense (con’t)
void dog(int x, int n)
{
if (x >= n)
cout << “Hello\n”;
else {
cout << x << ‘\t’ << n << endl;
dog(x+1, n-1);
}
}
CMSC 202
15
Approach to Writing Recursive Functions
Using “factorial” as an example,
1. Write the function header so that you are sure
what the function will do and how it will be
called.
[For factorial, we want to send in the integer
for which we want to compute the factorial.
And we want to receive the integer result back.]
int factorial(int n)
CMSC 202
16
Approach (con’t)
2. Decompose the problem into subproblems (if
necessary).
[For factorial, there are no subproblems. We
will see examples of subproblems later.]
3. Write recursive calls to solve those subproblems
whose form is similar to that of the original problem.
[Again, we will see subproblem examples later.
But there is a recursive call to write:
factorial(n-1)
CMSC 202
]
17
Approach (con’t)
4. Write code to combine, augment, or
modify the results of the recursive call(s)
if necessary to construct the desired
return value or create the desired side
effects.
[When a factorial has been computed,
the result must be multiplied by the
current value of the number for which
the factorial was taken:
return (n * factorial(n-1))
CMSC 202
]
18
Approach (con’t)
5. Write base case(s) to handle any
situations that are not handled
properly by the recursive portion of
the program.
[The base case for factorial is that if n=0,
the factorial is 1:
if (n == 0) return(1);
CMSC 202
]
19
Does It Work?
Using “factorial” as an example,
1. A recursive subprogram must have at
least one base case and one recursive
case (it's OK to have more than one base
case and/or more than one recursive case).
[ The first condition is met, because if
(n==0) return 1 is a base case, while the
"else" part includes a recursive call
(factorial(n-1)). ]
CMSC 202
20
Does It Work? (con’t)
2. The test for the base case must execute
before the recursive call.
[ If we reach the recursive call, we must
have already evaluated if (n==0); this is
the base case test, so this criterion is met. ]
CMSC 202
21
Does It Work? (con’t)
3. The problem must be broken down in such
a way that the recursive call is closer to the
base case than the top-level call.
[ The recursive call is factorial(n-1). The argument
to the recursive call is one less than the argument
to the top-level call to factorial. It is, therefore,
“closer” to the base case of n=0.]]
CMSC 202
22
Does It Work? (con’t)
4. The recursive call must not skip over the
base case.
[ Because n is an integer, and the recursive
call reduces n by just one, it is not possible
to skip over the base case. ]
CMSC 202
23
Does It Work? (con’t)
5. The non-recursive portions of the subprogram
must operate correctly.
[ Assuming that the recursive call works properly,
we must now verify that the rest of the code
works properly. We can do this by comparing the
code with our definition of factorial. This definition
says that if n=0 then n! is one. Our function correctly
returns 1 when n is 0. If n is not 0, the definition
says that we should return (n-1)! * n. The recursive
call (which we now assume to work properly)
returns the value of n-1 factorial, which is then
multiplied by n. Thus, the non--recursive portions
of the function behave as required. ]
CMSC 202
24
Recursion vs. Iteration
Recursion
 Usually less code – algorithm can be
easier to follow (Towers of Hanoi,
binary tree traversals, flood fill)
 Some mathematical and other
algorithms are naturally recursive
(factorial, summation, series expansions)
CMSC 202
25
Recursion vs. Iteration (con’t)
Iteration
 Use when the algorithms are easier
to write, understand, and modify
(especially for beginning programmers)
 Generally, runs faster because there
is no stack I/O
 Sometimes are forced to use iteration
because stack cannot handle enough
activation records (power(2, 5000))
CMSC 202
26
Fibonacci Numbers
The Fibonacci numbers can be defined by the rule:
fib(n) = 0 if n is 0,
= 1 if n is 1,
= fib(n-1) + fib(n-2) otherwise
For example, the first seven Fibonacci numbers are
Fib(0) = 0
Fib(1) = 1
Fib(2) = Fib(1) + Fib(0) = 1
Fib(3) = Fib(2) + Fib(1) = 2
Fib(4) = Fib(3) + Fib(2) = 3
Fib(5) = Fib(4) + Fib(3) = 5
Fib(6) = Fib(5) + Fib(4) = 8
CMSC 202
27
Tree Recursive Fibonacci
int fib(int n)
// Precondition: n >= 0
{
if (n == 0)
return 0;
if (n == 1)
return 1;
return (fib(n - 1) + fib(n - 2) );
}
CMSC 202
28
Tail Recursive Fibonacci
int fib_aux(int n, int next, int result)
// Precondition: n >= 0
{
if (n == 0)
return result;
return (fib_aux(n - 1, next + result, next) );
}
int fib(int n)
{
return fib(n, 1, 0);
}
CMSC 202
29
Linear Recursive Count_42s
int count_42s(int array[], int n)
{
if (n == 0)
return 0;
if (array[n-1] != 42) {
return (count_42s(array, n-1) );
}
return (1 + count_42s(array, n-1) );
}
CMSC 202
30
Tree Recursive Count_42s
int count_42s(int array[], int low, int high)
{
if ((low > high) ||
(low == high && array[low] != 42)) {
return 0 ;
}
if (low == high && array[low] == 42) {
return 1;
}
return (count_42s(array, low, (low + high)/2) +
count_42s(array, 1 + (low + high)/2, high)) );
}
CMSC 202
31
Floodfill
void Image::floodfill(int x, int y)
{
if (x < 0 || x >= numRows || y < 0 || y >= numCols) return;
if (a[x][y] == '1') return;
if (a[x][y] == '0') a[x][y] = '1';
floodfill(x+1, y);
floodfill(x-1, y);
floodfill(x, y-1);
floodfill(x, y+1);
// Go up
// Go down
// Go left
// Go right
}
CMSC 202
32