Recursion
n
n
n
n
n
n
General Form of Recursive methods
Examples of Simple Recursion
Hand Simulating Recursive methods
Proving Recursive methods Correct
Modeling Recursion via Onions
Recursive methods on Naturals/Integers
Recursion
n
n
Recursion is a programming technique in which a call
to a method appears in that method’s body (i.e., a
method calls itself: this is called direct recursion)
Once you understand recursive methods, they are
often simpler to write than their iterative equivalents

n
In modern programming languages, recursive methods may
run a bit slower (maybe 5%) than equivalent iterative
methods; in a typical application, this time is insignificant
(most of the time will be taken up elsewhere anyway)
We will begin by studying the form of general
recursive methods; then apply this form to methods
operating on int values; and finally apply that form to
methods operating on linked lists (where they are
most useful). In both cases we will discuss how
values of these types are recursively defined.
15-111
2
Fund Raising: Iteration vs. Recursion
15-111
3
Problem: Collect $1,000.00 for charity
Assumption: Everyone is willing to donate a penny
n
Iterative Solution

n
Visit 100,000 people, asking each for a penny
Recursive Solution


If you are asked to collect a penny, give a penny to the person
who asked you for it
Otherwise



Visit 10 people and ask them to each raise 1/10th of the amount of
money that you have been asked to raise
Collect the money that they give you and combine it into one bag
Give it to the person who asked you to collect the money
General Form of Recursive methods
Solve(Problem)
{
if (Problem is minimal/not decomposable: a base case)
solve Problem directly; i.e., without recursion
else {
(1) Decompose Problem into one or more similar,
strictly smaller subproblems: SP1, SP2, ... , SPN
(2) Recursively call Solve (this method) on each
subproblem: Solve(SP1), Solve(SP2),..., Solve(SPN)
(3) Combine the solutions to these subproblems into a
solution that solves the original Problem
}
}
15-111
4
factorial: In Mathematics and Java
1
if N = 0
N! =
N*(N-1)!
if N > 0
Example using Definition
4! = 4 * 3!
= 4 * 3 * 2!
= 4 * 3 * 2 * 1!
= 4 * 3 * 2 * 1 * 0!
=4*3*2*1*1
int factorial (int n)
{
if (n == 0)
//Non-decomposable
return 1;
else {
int subN = n-1;
//Decompose
int subFact = factorial(subN); //Solve Subproblem
return n * subFact;
//Combine
}
}
15-111
5
Simplified and Iterative factorial
int factorial (int n)
{
if (n == 0)
return 1;
else
return n * factorial(n-1);
}
int factorial (int n)
{
int answer = 1;
for (int i=1; i<=n; i++)
answer *= i;
return answer;
}
15-111
6
Here we combine the three
steps in the previous else
block into a single return
statement (one expression
including the decompose,
solve, and combine steps).
Compare this method to the
one below it, which operates
by iteration. The iterative
version requires the
declaration of two variables
and the use of state change
operators (which are always
difficult to reason about)
pow: Raising a Number to a Power
1
if N = 0
A*AN-1
if N > 0
AN =
double pow(double a, int n)
{
if (n == 0)
return 1.;
else
return a*pow(a,n-1)
}
The pow in the Java Math library
actually computes its answer using
logarithms and exponentials
Example using Definition
A4 = A * A3
= A * A * A2
= A * A * A * A1
= A * A * A * A * A0
= A * A* A* A* 1
Calling pow(a,n)requires
exactly n multiplications
15-111
7
Simulation of Recursive Methods
n
Assume that a method is computed according to its
definition by a person in an apartment complex

n
n
15-111
8
That person can be called to compute an answer; once he/she
computes the answer (possibly helped by calling another
person in the apartment complex), he/she places a return call,
and reports back the answer to the person who called him/her
Assume that each person knows the phone number of
the person living in the apartment underneath them,
who also has the same set of instructions: so any person
can call the one underneath to solve a simpler problem
The first method call initiates a sequence of calls to
people living in lower level apartments (each person
solving a simpler problem), whose answers percolate
back to the top, finally solving the original problem
Hand Simulation of Factorial
n
=
return =
n
=
return =
n
=
return =
n
=
return =
...
n
=
return =
15-111
9
Proof Rules for Recursive Methods
To prove that a recursive method, Solve, is correct:
n Prove that Solve computes (without recursion) the
correct answer to any minimal (base case) Problem

n
Prove that the argument to any recursive call of
Solve, e.g. SPI, is strictly smaller (closer to the
minimal case) than Problem

n
Base cases are simple, so this should be easy
The notion of strictly smaller should be easy to understand
for the recursive argument, so this should be easy
Prove that these answers are combined to compute
the correct answer for Problem


In this proof, you may assume that each recursive call,
Solve(SPI), correctly computes its answer
The assumption makes this proof easy
Recursion is computable induction (a math concept)
15-111
10
Applying the Proof Rules
15-111
11
factorial (recurring on the parameter n)
n factorial correctly returns 1 for the minimal argument 0.
n In factorial(n-1), n-1 is always closer to 0 than n is.
n Assume factorial(n-1) computes the correct answer.

n times this value is, by definition, the correct value of
factorial(n)
pow (recurring on the parameter n)
n pow correctly returns 1 for the minimal argument 0.
n In pow(a,n-1), n-1 is always closer to 0 than n is.
n Assume pow(a,n-1) computes the correct answer, an-1.

a*pow(a,n-1) is a*an-1 is an, the correct value of pow(a,n)
Proof Rules and Bad Factorials
int factorial (int n)
{
if (n == 0)
return 0;
else
return n*factorial(n-1);
}
int factorial (int n)
{
if (n == 0)
return 1;
else
return factorial(n+1)/(n+1);
}
int factorial (int n)
{
if (n == 0)
return 1;
else
return n + factorial(n-1);
}
//0! is not 0;
//n+1 not closer to 0
//n+(n-1)! is not n!
15-111
12
Proof Rules and Bad Factorials (cont)
n
n
n
n
15-111
13
In the first method, the wrong answer (0) is returned for the base
case; since everything depends on the base case, ultimately this
method always returns 0
In the second method, n+1 is farther away from the base case: this
method will continue calling factorial with ever larger arguments,
until the maximum int value is exceeded: a runaway (or “infinite”)
recursion (actually, each recursive call can take up some space, so
eventually memory is exhausted).
In the third method, the wrong answer is returned by incorrectly
combining n and the solved subproblem; this method returns one
more than the sum of all the integers from 1 to n (an interesting
method in its own right) not the product of these values
In the first method, it always returns the wrong answer; the
second method never returns an answer, the third method returns
the correct answer only in the base case
fpow: a faster version of pow
1
if N = 0
AN = B2 where B = AN/2 if N > 0 and N is Even
AB2 where B = AN/2 if N > 0 and N is Odd
int fpow(double a, int n)
{
if (n == 0)
return 1.;
else {
double b = fpow(a,n/2);
if (n%2 == 0)
return b*b;
else
return a*b*b;
}
}
15-111
14
Note: if N
is odd N/2
truncates:
so 7/2 = 3
Calling fpow(a,n)
requires between at least log2n and
at most 2log2n multiplications
Compare this complexity to calling
pow(a,n)requiring n multiplications
Contemporary cryptography raises
large numbers to huge (hundred
digit) powers; it needs a fast method
Recursive Definition of Naturals
n
0 is the smallest Natural


n
It is minimal, and cannot be decomposed
z(x) is true if x is zero and false if x is non-zero
The successor of a Natural is a Natural

If x is a Natural, s(x) is a Natural


The successor of x is x+1
If x is a non-0 Natural, p(x) is a Natural


The predecessor of x is x-1
p(0) throws an exception
Note:
z(s(x)) is always false
p(s(x)) = x
s(p(x)) = x only if X  0
15-111
15
Onion Model of Recursive Naturals
15-111
16
Every Onion is either
Base Case
: The core
Recursive Case: A layer of skin around a smaller onion
(which may be the core, or some deeper layer)
The value of an onion is the number of layers of skin beyond the core
0
s(0) = 1
s(s(0)) = 2
s(s(s(0))) = 3
Computation with Naturals
15-111
17
Let’s Define 3 methods that operate on Naturals in Java
int s(int x) {return x+1;}
int p(int x)
{
if (x==0)
throw new IllegalArgumentException("p with x=0");
return x-1;
}
bool z(int x) {return x == 0;}
We can define all common operators (both arithmetic and
relational) on Naturals by writing simple recursive methods
that use these three methods
Recursive methods on Naturals
int sum(int a, int b)
{
if (z(a))
return b;
else
return s(sum(p(a),b));
}
int sum(int a, int b)
{
if (z(a))
return b;
else
return sum(p(a), s(b));
}
//1 + (a-1 + b)
//(a-1) + (b+1)
In both sum methods, a gets closer to 0 in recursive calls
15-111
18
Recursive methods on Naturals II
int product(int a, int b)
{
if (z(a))
return 0;
else
return sum(b,product(p(a),b)) //b + (a-1)*b
}
int power(int a, int b)
{
if (z(b))
return 1;
else
return product(a, power(a,p(b)));//a * ab-1
}
15-111
19
Recursive methods on Naturals III
15-111
20
bool equal(int a, int b)
//Is a == b
{
if (z(a) || z(b))
//If either is 0...
return z(a) && z(b);
//return whether both are 0
else
return equal(p(a), p(b)); //Is (a-1) == (b-1)
}
bool less(int a, int b)
{
if (z(b))
return false;
else if (z(a))
return true;
else
return less(p(s),p(b));
}
//Is a < b
//Nothing is < 0
//If b!=0, a==0, then a<b
//Is (a-1) < (b-1)
Recursive methods on Naturals IV
bool even(int a)
{
if (z(a))
return true;
else
return !even(p(a))
}
bool odd(int a)
{
if (z(a))
return false;
else
return !odd(p(a));
}
//True if 0
//Opposite of even(a-1)
//False if 0
//Opposite of odd(a-1)
15-111
21
Printing an Integer’s Digits
15-111
22
void print (int i)
{
if (i < 10)
//if (i >= 10)
System.out.print(i);
// print(i/10);
else {
//System.out.print(i%10);
print(i/10);
The code above is simplified by
System.out.println(i%10);
bottom factoring and test reversal
}
and noting for i<10, i is i%10
}
n
n
n
print correctly prints all 1-digit values: 0 - 9.
In print(i/10), i/10 is one digit closer to 0 - 9 than i is.
Assume print (i/10) correctly prints all the digits in i/10
in the correct order

Printing i/10 (all digits but the last) and then printing i%10 (the
last digit), prints all the digits in i in order
Printing an Integer’s Digits in Reverse
15-111
23
void printReversed (int i)
{
if (i < 10)
//System.out.print(i%10);
System.out.print(i);
//if (i >= 10)
else {
// System.out.print(i/10);
System.out.print(i%10);
printReversed(i/10);
}
}
n
n
n
printReversed correctly prints all 1-digit values: 0 - 9.
In printReversed(i/10), i/10 is closer to 0-9 than i is.
Assume printReversed(i/10) correctly prints all the
digits in i/10 reversed.

Printing the last digit, i%10, and then printing the i/10 reversed
prints all the digits in i reversed.
Converting an int to a string
15-111
24
String toString (int i)
{
if (i < 10)
return ""+(char)(i+’0’);
else
return toString(i/10) + (char)(i%10+’0’);
}
n
n
n
toString correctly returns all 1-digit values: 0 - 9.
In toString(i/10), i/10 is one digit closer to 0-9 than i is.
Assume toString(i/10) correctly returns a String of all the
digits in I/10.

Then, after appending the char equivalent of i%10 at the end of
this String correctly stores the String equivalent of i.
Synthesizing Recursive Methods
n
Find the base (non-decomposable) case(s)

n

n
Write the code that detects the base case(s) and returns the
correct answer for them without using recursion
Assume that you can decompose all non base-case(s)
and then solve these smaller subproblems via recursion

n
15-111
25
Choose the decomposition
There should be some natural decomposition
Write code that combines these solved subproblems
(often there is just one) to solve the original problem
Typical decompositions


Integers
: i - something or i/something (digit at a time)
Linked Lists: l.next
Problems
n
n
15-111
26
Write the following method
public static String reverse (String s) recursively.
Choose an appropriate base case, recursive call (hint:
substring method using one parameter), and a way to
combine (hint: +) solved smaller problems to solve the
original problem.
reverse("abcd") should return "dcba"
Write the following method
public static int toInt (String s) recursively. It is like
parseInt, but only for non-negative values
toInt("138") should return 138
Problems (continued)
n
n
Write the following method
public static boolean
equals (String s1, String s2) recursively. Its
recursive structure is like that of the equals methods
for ints.
Write the following method
public static int
compare (String s1, String s2) recursively. Its
recursive structure is similar to equals, above.
15-111
27
Descargar

Windows NT/Borland C++ IDE - Carnegie Mellon University