Data Structures CSCD 300
Eastern Washington University
Popular in Course
Popular in ComputerScienence
This 22 page Class Notes was uploaded by Dewitt Paucek on Sunday October 11, 2015. The Class Notes belongs to CSCD 300 at Eastern Washington University taught by Staff in Fall. Since its upload, it has received 32 views. For similar materials see /class/221503/cscd-300-eastern-washington-university in ComputerScienence at Eastern Washington University.
Reviews for Data Structures
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/11/15
Recursion CSCD 326 Slide 1 2106 Proof by Induction Introduction only topic will be covered in detail in CS 327 Prove Z iNN12 i1 Basis Step show true for trivial case here N 1 forN1thesum is 11 1 21 CSCD 326 Slide 2 2106 Proof by Induction Inductive hypothesis statement is true for N k Inductive step if true for N k show true for N k 1 k1 k 2i k1Zi i1 i1 CSCD 326 Slide 3 2106 Proof by Induction Inductive step k1 Zik1kk12k1k22 i1 so by induction the statement is true for all k cscn 326 Slide 4 2106 Recursion 0 Math definition a a solution to a problem that is defined in terms of a simpler version of itself 0 Programming definition 0 a function which calls itself CSCD 326 Slide 5 2106 Recursion e Recursive definition of Sum of Integers public static int Sum int n assumes n is gt1 if n 1 return 1 else return Sum n 1 n CSCD 326 Slide 6 2106 Factorial Mathematical Definition Mathem tical definition recursive 1 if N1 or NO N NN1 if Ngt1 CSCD 326 Slide 7 2106 Factorial Recursive Method Recursive method for factorial public static int factorial int n int temp SystemoutprintlnquotEntering factorial n quot n mm nmm temp 1 else temp n factorialn1 SystemoutprintlnquotLeaving factorial n quot n return temp Call SystemoutprintlnquotFactorial4quot factorial4 CSCD 326 Slide 8 2106 Stack Frames System Stack used to control which function is currently active and to reverse the order of function calls when returning Stack Frame a variable size piece of memory that is pushed onto thedsystem stack each time a function call is ma e CSCD 326 Slide 9 2106 Stack Frames Stack Frame contains 0 space for all local automatic variables 0 the return address the place in the program to which execution will return when this function ends 0 the return value from the function 0 all parameters for a function with actual parameter values copied in The stack frame on top of the stack always represents the function being executed at any point in time only the stack frame on top of the stack is accessible at any time csco 326 Slide 10 2105 Factorial Trace Return Addr 1 N 4 Return Val System Stack output CSCD 326 Slide 11 2106 Rules of Recursion 0 Always include a terminal case which does not require recursion to calculate a Each recursive call should progress toward the terminal case 0 Assume each recursive call works when designing a recursive algorithm csco 326 Slide 12 2106 Recursive Array Printing public class ArrayPrintDriver public static void printem int array int n int last ifn lt last Systemoutprintln arrayn printemarray n 1 last9 public static void main String args int values new int5 forint i 0 i lt 5 i valuesi i1 printemvalues 0 4 0 cscn 326 Slide 13 2106 Array Printing Trace Ret Addr last 4 larray values n 2 0 CSCD 326 Slide 14 2106 Multiple Recursion Fibonacci Sequence 0 1 1 2 3 5 8 13 21 44 oeach number in sequence is the sum of the previous two numbers except the first two eFibonacci number 0 O Fibonacci number 1 1 call other Fibonacci numbers are defined as the sum of the previous two csco 326 Slide 15 2106 Multiple Recursion public static int fib int n if n lt 1 return n else return fib n 1 fib n 2 Problem multiple calls are made to calculate the same Fibonacci number cscn 326 Slide 16 2106 Problems with Recursion 3 Memory stack exhaustion e if many stack frames are pushed can run out of space for stack 0 if each call allocates much memory either automatically or dynamically heap exhaustion is possible 0 Time 8 each recursive call requires time to set up a new stack frame copy in actual parameter values and transfer execution csco 326 Slide 17 2106 Problems with Recursion Any recursive algorithm can be rewritten using iterative technique it will be longer and more likely to have problems but will run faster csco 326 Slide 18 2106 Recursive Binary Search public int binarySearchComparable anArray Comparable target int left int right ifright lt left return 1 ll target not present else int mid left right I 2 if targetcompareToanArraymid 0 return mid if targetcompareToanArraymid lt 0 return binarySearchanArray target left mid 1 else return binarySearchanArray target mid1 right ll end else cscn 326 Slide 19 2106 Binary Search Analysis 0 Worst case target is not found Analysis proceeds in the same way as for the iterative version only the number of passes is replaced by the number of calls to binarySearch csco 326 Slide 22 2106 Towers of Hanoi Problem disks of varying diameter are all on one peg of three with the largest disks on the bottom and the smallest on the top Goal move all disks from peg A to peg C Rules must move one disk at a time can not place a larger disk on a smaller disk quotl lil th l w a w csco 326 Slide 23 2105
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'