03-Recursion.ppt

Recursion and Induction Algorithm : Design Analysis [3] In the last class… Asymptotic growth rate The Sets ?, ? and ? Complexity Class An Example: Searching an Ordered Array Improved Sequential Search Binary Search Binary Search Is Optimal Recursion and Induction Recursive Procedures Analyzing the Recursive Computation. Induction over Recursive Procedures Proving Correctness of Procedures Thinking Recursively: Problem 1 Towers of Hanoi How many moves are need to move all the disks to the third peg by moving only one at a time and never placing a disk on top of a smaller one. Thinking Recursively: Problem 2 Cutting the plane How many sections can be generated at most by n straight lines with infinite length. Recursion: General Pattern Method99 If the task is to write a procedure p for a problem of size 0 to 100, and There exists a ready-to-use subroutine p99, that can provide the solution for the same problem of size 0-99, then Just figure out a way to write p by calling p99 when needed. IntList delete IntList L, int x IntList newL, fixedL; if L nil newL L; else if x first L newL rest L ; else fixedL delete99 rest L ,x ; newL cons first L ,fixedL return newL Thinking Recursively: Problem 3 Josephus’s problem Find the position to live, or die! Recursion: an Implementation View Activation Frame Basic unit of storage for an individual procedure invocation at run time Providing a frame of reference in which the procedure executes for this invocation only Space is allocated in a region of storage called the frame stack Activation trace Fibonacci Function: An Example int fib int n int f, f1, f2; if n 2 f n; else f1 fib n-1 ; f2 fib n-2 ; f f1+f2; return f; Loop-free Complexity In a computation without while or for loops, but possibly with recursive procedure calls, The time that any particular activation frame is on the top of the frame stack is O L , where L is the number of lines in the procedure that contain either a simple statement or a procedure call.