Transcript Document
4.4 Recursive Algorithms
• A recursive algorithm is one which calls itself
to solve “smaller” versions of an input
problem.
• How it works:
– The current status of the algorithm is placed on a
stack.
• A stack is a data structure from which entries
can be added and deleted only from one end.
1
• like the plates in a cafeteria:
• PUSH: put a 'plate' on the stack.
• POP: take a 'plate' off the stack.
• When an algorithm calls itself, the current activation
is suspended in time and its parameters are PUSHed
on a stack.
• The set of parameters need to restore the algorithm
to its current activation is called an activation record.
2
• Example:
procedure factorial (n)
/* make the procedure idiot proof */
if n < 0 return 'error'
if n = 0 then return 1
else
return n factorial (n-1)
• Algorithm 1 A Recursive Algorithm for Computing n!
procedure factorial (n: nonnegative integers)
if n=0 then factorial(n) :=1
else factorial(n) := n．factorial(n-1)
3
The operating system supplies all the necessary facilities to
produce:
factorial (3): PUSH 3 on stack and call
factorial (2): PUSH 2 on stack and call
factorial (1): PUSH 1 on stack and call
factorial (0): return 1
POP 1 from stack and return (1) (1)
POP 2 from the stack and return (2) [(1) (1)]
POP 3 from the stack and return (3) [(2) [(1) (1)]]
• Complexity:
• Let f(n) be the number of multiplications required to
compute factorial (n).
f(0) = 0: the initial condition
f(n) = 1 + f(n-1): the recurrence equation
4
• Hw :example 2 (p.312) Give a recursive algorithm for
computing an, where a is a nonzero real number and
n is a nonnegative integer.
• Example:
• A recursive procedure to find the max of a nonvoid
list.
• Assume we have a built-in functions called
– Length which returns the number of elements in a
list
– Max which returns the larger of two values
– Listhead which returns the first element in a list
– Remain which returns the remainder of the list
• Max requires one comparison.
5
procedure maxlist (list)
/* strip off head of list and pass the remainder */
if Length(list) = 1 then
return Listhead(list)
else
return Max( Listhead(list), maxlist
(Remain (list)))
• The recurrence equation for the number of
comparisons required for a list of length n, f(n), is
f(1) = 0
f(n) = 1 + f(n-1)
6
• Example:
If we assume the length is a power of 2:
– We divide the list in half and find the maximum of
each half.
– Then find the Max of the maximum of the two
halves.
procedure maxlist2 (list)
/* a divide and conquer approach */
if Length (list) = 1 then
return Listhead(list)
else
a = maxlist2 (fist half of list)
b = maxlist2 (second half of list)
return Max{a, b}
7
• Recurrence equation for the number of
comparisons required for a list of length n, f(n),
is
f(1) = 0
f(n) = 2 f(n/2) + 1
• There are two calls to maxlist each of which
requires f(n/2) operations to find the max.
• There is one comparison required by the Max
function.
8
Recursion and Iteration
• Algorithm 7 A Recursive
Algorithm for Fibonacc
Numbers.
procedure fibonacci (n:
nonnegative integers)
if n=0 then
fibonacci(0) :=0
else if n=1 then
fibonacci(1) :=1
else fibonacci(n) :=
fibonacci(n-1) +
fibonacci(n-2)
• Algorithm 8 An Iterative
Algorithm for Computing
Fibonacci Numbers.
procedure iterative fibonacci
(n: nonnegative integers)
if n=0 then y :=0
else
begin
x :=0
y :=1
for i :=2 to n
begin
z :=x+y
x :=y
y :=z
end
End
{z is the nth Fibonacci number}
9
Recursive Algorithm for Fibonacci Number
10
The Merge Sort
• Example 9: Sort the list 8, 2, 4, 6, 9, 7, 10, 1, 5, 3
using the merge sort.
• Algorithm 9 A Recursive Merge Sort.
Procedure mergesort(L= a1, . . . , an)
If n=1 then return L
If n> 1 then
Begin
m :=n/2
L1 := a1, a2, . . . ,am
L2 := am+1, am+2, . . ., an
return merge(mergesort(L1), mergesort(L2))
End
{The return value is now sorted into nondecreasing order}
11
FIGURE 2 The
Merge Sort of
8,2,4,6,9,7,10,1,5,3.
12
13