Transcript Recursion

Recursion
n! (n factorial)


The number of ways n objects can be
permuted (arranged).
For example, consider 3 things, A, B, and C.

1.
2.
3.
4.
5.
6.

3! = 6
ABC
ACB
CAB
CBA
BCA
BAC
The first few factorials for n=0, 1, 2, ... are 1,
1, 2, 6, 24, 120, ...
n! (n factorial)
 n! for some non negative integer n is defined
as:
 n! = n * (n-1) * (n-2) * … * 2 * 1
 0! is defined as 1.
 From
http://mathworld.wolfram.com/Factorial.html
n! (n factorial)
 n! for some non negative integer n can
be rewritten as:
 0! = 1
 1! = 1
 n! = n * (n-1)!
for n = 0
for n = 1
for all other n > 1
Triangular numbers
 The triangular number Tn can be
represented in the form of a triangular
grid of points where the first row contains
a single element and each subsequent
row contains one more element than the
previous one. The triangular numbers
are therefore 1, 1+2, 1+2+3, 1+2+3+4, ...,
so the first few triangle numbers are 1, 3,
6, 10, 15, 21, ...
Triangular numbers
n
Tn   k
k 0
 which can also be expressed as:
 Tn = 1
 Tn = n + Tn-1
for n = 1
for n > 1
 From
http://mathworld.wolfram.com/Triangular
Number.html
Triangular numbers
A plot of the first few triangular numbers
represented as a sequence of binary bits is
shown below. The top portion shows T1 (1, 3,
6, 10, 15, 21, …) to T255, and the bottom shows
the next 510 values.
000001
000110
001011
011110
110011
Recurrence relation
 In mathematics, a recurrence relation is an
equation that defines a sequence recursively:
each term of the sequence is defined as a
function of the preceding terms.
 A difference equation is a specific type of
recurrence relation.
 Some simply defined recurrence relations can
have very complex (chaotic) behaviors and are
sometimes studied by physicists and
mathematicians in a field of mathematics
known as nonlinear analysis.
 From
http://en.wikipedia.org/wiki/Recurrence_relation
Fibonacci numbers
 The sequence of Fibonacci numbers
begins: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
89, 144, ...
F0  0
F1  1
Fn  Fn 1  Fn  2
Mathematical induction




The idea of sequences in which later terms are
deduced from earlier ones, which is implicit in the
principle of mathematical induction, dates to antiquity.
The truth of an infinite sequence of propositions Pi for
i=1, ...,  is established if
1. P1 is true, and
2. Pk implies Pk+1 for all k.
This principle is sometimes also known as the method
of induction.
From
http://mathworld.wolfram.com/RecursiveSequence.ht
ml and
http://mathworld.wolfram.com/PrincipleofMathematical
Induction.html
Mathematical induction
 The idea of sequences in which later
terms are deduced from earlier ones,
which is implicit in the principle of
mathematical induction, dates to
antiquity.
 The truth of an infinite sequence of
propositions Pi for i=1, ...,  is
base case(s)
established if
1. P1 is true, and
2. Pk implies Pk+1 for all k.
inductive case(s)
Back to n! (n factorial)
 n! for some non negative integer n can
be rewritten as:
base cases
 0! = 1
 1! = 1
 n! = n * (n-1)!
for n = 0
for n = 1
for all other n > 1
inductive
case
Let’s code n! (n factorial)
 n! for some non negative integer n can be
rewritten as:
 0! = 1
for n = 0
 1! = 1
for n = 1
 n! = n * (n-1)! for all other n > 1
public static int nFactorial ( int n ) {
}
base cases
inductive
case
Let’s code n! (n factorial)
 n! for some non negative integer n can be
rewritten as:
 0! = 1
for n = 0
 1! = 1
for n = 1
 n! = n * (n-1)! for all other n > 1
public static int nFactorial ( int n ) {
//base cases
if (n==0)
return 1;
}
base cases
inductive
case
Let’s code n! (n factorial)
 n! for some non negative integer n can be
rewritten as:
 0! = 1
for n = 0
 1! = 1
for n = 1
 n! = n * (n-1)! for all other n > 1
public static int nFactorial ( int n ) {
//base cases
if (n==0)
return 1;
if (n==1)
return 1;
}
base cases
inductive
case
Let’s code n! (n factorial)
 n! for some non negative integer n can be
rewritten as:
 0! = 1
for n = 0
 1! = 1
for n = 1
 n! = n * (n-1)! for all other n > 1
public static int nFactorial ( int n ) {
//base cases
if (n==0)
return 1;
if (n==1)
return 1;
return n * nFactorial( n-1 );
}
base cases
inductive
case
Let’s code n! (n factorial)
 n! for some non negative integer n can be
rewritten as:
 0! = 1
for n = 0
 1! = 1
for n = 1
 n! = n * (n-1)! for all other n > 1
public static int nFactorial ( int n ) {
//base cases
This is an example of a
if (n==0)
return 1;
recursive function (a
function that calls
if (n==1)
return 1;
return n * nFactorial( n-1 ); itself)!
}
To use this function:
int result = nFactorial( 10 );
Back to Triangular
numbers
 Tn = 1
 Tn = n + Tn-1
for n = 1
for n > 1
 What is the base case(s)?
 What is the inductive case?
 How can we write the code for this?
Back to Fibonacci
numbers
 The sequence of Fibonacci numbers
begins: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
89, 144, ...
What is the base case(s)?
F0  0
What is the inductive case?
F1  1
How can we code this?
Fn  Fn 1  Fn  2
A more interesting
example
 “Combinatorics is a branch of pure mathematics
concerning the study of discrete (and usually finite)
objects. It is related to many other areas of
mathematics, such as algebra, probability theory,
ergodic theory and geometry, as well as to applied
subjects such as computer science and statistical
physics. Aspects of combinatorics include "counting"
the objects satisfying certain criteria (enumerative
combinatorics), deciding when the criteria can be met,
and constructing and analyzing objects meeting the
criteria (as in combinatorial designs and matroid
theory), finding "largest", "smallest", or "optimal"
objects (extremal combinatorics and combinatorial
optimization), and finding algebraic structures these
objects may have (algebraic combinatorics).”
from http://en.wikipedia.org/wiki/Combinatorics
A more interesting
example
 In how many different ways can we select 2 out of 3
playing cards {A,B,C} (w/out regard to order)?
 A B
 A C
 B C
 Generally called Combinations w/out Repetitions (the
Binomial Coefficient):
 where n is the number of objects from which you can
choose, and k is the number to be chosen.
Combinatorics
 Say we don’t have a closed-form solution
for the “n choose k” problem.
 Let’s develop the base cases first.
 How many ways can we choose k things out
of n things (without regard to order) when k
= 1?
Combinatorics
 Let’s develop the base cases first.
B1. How many ways can we choose k things
out of n things (without regard to order)
when k = 1 (i.e., choose 1 from n things)?
 Answer: n so ways( k, n ) = n for k=1.
Combinatorics
 Let’s develop the base cases first.
B2. How many ways can we choose k things
out of n things (without regard to order)
when k = n (i.e., choose all n things from n
things)?
Combinatorics
 Let’s develop the base cases first.
B2. How many ways can we choose k things
out of n things (without regard to order)
when k = n (i.e., choose all n things from n
things)?
 Answer: 1 so ways( k, n ) = 1 for k=n.
Combinatorics
 Now let’s develop the inductive case.
 Ex. ways( 2, 3 ) = 3
1 2
1 3
2 3
 Say we always pick card 3.
 Then we can only get 1 3 and 2 3.
 So we are only free to pick 1 or 2 and we have already
said that ways(1,2)=2 which more generally is:
 ways( k-1, n-1 )
Combinatorics
 Now let’s develop the inductive case.
 Ex. ways( 2, 3 ) = 3
1 2
1 3
2 3




Say we don’t pick card 3.
Then we can only pick 1 2.
So we can only pick 2 things out of two things.
We have already noted that ways( 2, 2 ) = 1 which more
generally is:
 ways( k, n-1 )
Combinatorics
 So our inductive case is:
 ways( k, n ) = ways( k-1, n-1 )
+ ways( k, n-1 )
for 1<k<n
Combinatorics
 Putting it all together . . .
 ways( k, n ) = n for k=1
 ways( k, n ) = 1 for k=n
 ways( k, n ) = ways( k-1, n-1 )
+ ways( k, n-1 )
for 1<k<n
Combinatorics
 Rules:
 ways( k, n ) = n for k=1
 ways( k, n ) = 1 for k=n
 ways( k, n ) = ways( k-1, n-1 ) + ways( k, n-1 )
for 1<k<n
 Code: (example: ways( 5, 10 ) = 252)
public static int ways ( int k, int n ) {
if (k==1)
return n;
if (k==n)
return 1;
return ways( k-1, n-1 ) + ways( k, n-1 );
}
A final note regarding
recursion . . .
 Calculations such as factorial, Fibonacci
numbers, etc. are fine for introducing the
idea of recursion.
 But the real power of recursion (IMHO) is
in traversing advanced data structures
such as trees (covered in more advanced
classes and used in such as applications
as language parsing, games, etc.).