Transcript Int factorial(int N)

Data Structures & Algorithms
sion and Trees
Richard Newman
Recursion
• Fundamental concept in math and CS
• Recursive definition
• Defined in terms of itself
• aN = a*aN-1, a0 = 1
• Recursive function
• Calls itself
• int exp(int base, int pow) {
• return (pow == 0? 1 : base*exp(base, pow));
Recursion
Recursive definition (and function) must:
• 1. have a base case – termination condition
• 2. always call a case smaller than itself
•
All practical computations can be couched in a
• (see theory of computation)
•
•Trees
Recursively defined structures
• e.g., binary tree
• Base case:
–Empty tree has no nodes
• Recursion:
–None-empty tree has a root node with two c
•
ap to Recursion
•






Widely used in CS and with trees...
Mathematical recurrences
Recursive programs
Divide and Conquer
Dynamic Programming
Tree traversal
DFS
ive Algorithms
•
•
Recursive algorithm – solves problem by solving one
Recurrence relation – factorial
– N! = N(N-1)!, for N > 0, with 0! = 1.
– In C++, use recursive functions
Int factorial(int N)
{
if (N == 0) return 1;
return N*factorial(N-1);
}
ive Algorithms
•
•
BTW, can often also be expressed as iteration
E.g., can also write N! computation as a loop:
int factorial(int N)
{
for (int t = 1, i = 1; i <= N; ++i)
t *= i;
return t;
}
d's Algorithm
•
•
Euclid's Algorithm is one of the oldest known algorithm
Recursive method for finding the GCD of two integers
int gcd(int m, int n)
{
// expect m >= n
if (n == 0) return m;
return gcd(n, m % n);
}
Recursive call to
smaller instance
Base case
e & Conquer
Recursive scheme that divides input into two
• Then makes a recursive call on each part
• Widely used approach
• Many important algorithms
• Depending on expense of dividing and combi
•
e & Conquer
•
•
•
•
•
•
Example: find the maximum element in an array a[N
Easy to do iteratively...
Base case:
– Only one element – return it
Divide:
– Split array into upper and lower halves
Recursion:
– Find maximum of each half
Combine results:
– Return larger of two maxima
e & Conquer
•
Property 5.1: A recursive function that divides a problem of size N into two indep
•
Prf:
 T(1) = 0
 T(N) = T(k) + T(N-k) + 1 for recursive call on size N
 Induct!
wer of Hanoi
•
•
•
•
•
•
•
•
3 pegs
N disks, all on one peg
Disks arranged from largest on bottom to smalle
Must move all disks to target peg
Can only move one disk at a time
Must place disk on another peg
Can never place larger disk on a smaller one
Legend has it that the world will end when a cert
wer of Hanoi
Which peg should
top disk go on first?
Target peg
wer of Hanoi
How many moves does this take?
How many moves does this take?
wer of Hanoi
Property 5.2: The recursive d&c algorithm for the
Towers of Hanoi problem produces a solution
that has 2N – 1 moves.
Prf:
T(1) = 1
T(N) = T(N-1) + 1 + T(N-1) = 2 T(N-1) + 1
= 2N – 1 by induction
e & Conquer
•
Two other important D&C algorithms:
•
Binary search
MergeSort
•
Algorithm/metri Recurrence
c
Approx.
Soln.
Binary Search
comparisons
C(N) = C(N/2)+1
lg N
MergeSort
recursive
calls
A(N) = 2 A(N/2) +
1
N
MergeSort
comparisons
C(N) = 2 C(N/2) +
N
N lg N
c Programming
•
•
•
In Divide & Conquer, it is essential that the subproblem
When this is not the case, life gets complicated!
Sometimes, we can essentially fill up a table with valu
c Programming
•
Fibonacci Numbers:
 F[0] = 0
 F[1] = 1
 F[N] = F[N-1] + F[N-2]
•
Horribly inefficient implementation:
int F(int N)
{
if (N < 1) return 0;
if (N == 1) return 1;
return F(N-1) + F(N-2);
}
c Programming
•
•
•
•
How bad is this code?
How many calls does it make to itself?
F(N) makes F(N+1) calls!
Exponential!!!!
13
8
5
5
3
2
3
2
1
1 0
1
1
1
1 0
1 0
1
2
1
1
1 0
1
2
3
1 0
2
1
1 0
1
1
1
1 0
1 0
1
c Programming
•
•
•
•
Can we do better?
How?
Make a table – compute once (yellow shapes)
Fill up table
13
8
5
5
3
2
3
2
1
1 0
1
1
1
1 0
1 0
1
2
1
1
1 0
1
2
3
1 0
2
1
1 0
1
1
1
1 0
1 0
1
c Programming
•
Property 5.3: Dynamic Programming reduces the runn
•Trees
•
•
•
A mathematical abstraction
Central to many algorithms
 Describe dynamic properties of algorithms
 Build and use explicit tree data structures
Examples:
 Family tree of descendants
 Sports tournaments (Who's In?)
 Organization Charts (Army)
 Parse tree of natural language sentence
 File systems
pes of Trees
•
•
•
•
Trees
Rooted trees
Ordered trees
M-ary trees and binary trees
•
•
•
Defn: A Tree is a nonempty collection of vertices and e
Defn: A path is a list of distinct vertices such that succ
Defn: A graph in which there is at most one path betw