Recursion Jan 13 2019 Definitions I A recursive definition is a definition in which the thing being defined occurs as part of its own definition Example An atom is a name or a number A list consists of An open parenthesis Zero or more atoms or lists and A close parenthesis 2 Definitions II Indirect recursion is when a thing is defined in terms of other things but those other things are defined in terms of the first thing Example A list is An open parenthesis Zero or more S expressions and A close parenthesis An S expression is an atom or a list 3 Recursive functions er methods The mathematical definition of factorial is factorial n is We can define this in Java as 1 if n 1 n factorial n 1 otherwise long factorial long n if n 1 return 1 else return n factorial n 1 This is a recursive function because it calls itself Recursive functions are completely legal in Java 4 Anatomy of a recursion Base case does some work without making a recursive call long factorial long n if n 1 return 1 else return n factorial n 1 Extra work to convert the result of the recursive call into the result of this call Recursive case recurs with a simpler parameter 5 Infinite recursion The following is the recursive equivalent of an infinite loop int toInfinityAndBeyond int x return toInfinityAndBeyond x While this is obviously foolish infinite recursions can happen by accident in more complex methods 6 Another problem Consider the following code fragment int n 20 int factorial if n 1 return 1 else n n 1 return n 1 factorial Does this work Changing a non local variable makes the program much more difficult to understand 7 Why recursion For something like the factorial function which is sort of the Hello world of recursion it s faster and just as simple to use a loop For working with inherently recursive data such as arithmetic expressions recursion is much simpler Recall the definition of a list Example To evaluate the expression 2 3 4 5 you must first evaluate the expressions 2 3 and 4 5 A list consists of An open parenthesis Zero or more atoms or lists and A close parenthesis Lists are also inherently recursive 8 Understanding recursion The usual way to teach recursion is to trace through a recursion seeing what it does at each level This may be a good way to understand how recursion works but it s a terrible way to try to use recursion There is a better way 9 Base cases and recursive cases Every valid recursive definition consists of two parts One or more base cases where you compute the answer directly without recursion One or more recursive cases where you do part of the work and recur with a simpler problem 10 Information hiding function spread int A int size int max min sort A size min A 0 max A size 1 return max min Can you understand this function without looking at sort 11 Stepping through called functions Functions should do something simple and understandable When you try to understand a function you should not have to step through the code of the functions that it calls When you try to understand a recursive function you should not have to step through the code of the functions it calls 12 We have small heads It s hard enough to understand one level of one function at a time It s almost impossible to keep track of many levels of the same function all at once But you can understand one level of one function at a time and that s all you need to understand in order to use recursion well 13 The four rules Do the base cases first Recur only with a simpler case Don t modify non local variables Don t look down Remember parameters count as local variables 14 Do the base cases first Every recursive function must have some things it can do without recursion These are the simple or base cases Test for these cases and do them first This is just writing ordinary nonrecursive code 15 Recur only with a simpler case If the problem isn t simple enough to be a base case break it into two parts A simpler problem of the same kind for example a smaller number or a shorter list Extra work not solved by the simpler problem Combine the results of the recursion and the extra work into a complete solution Simpler means more like a base case 16 Example 1 member Is value X a member of list L boolean member X L if L is the empty list return false this is a base case if X equals the first element in L return true another base case return member X L first element simpler because more like empty list 17 Example 2 double Double every element of a list of numbers function double L if L is the empty list return the empty list base case else L2 double L first element recur D 2 first element in L extra work return list made by adding D to L2 combine 18 It s OK to modify local variables A function has its own copy of local variables parameters passed by value which are effectively local variables Each level of a recursive function has its own copy of these variables and parameters Changing them at one level does not change them at other levels One level can t interfere with another level 19 It s bad to modify objects There is typically only one copy of a given object If a parameter is passed by reference there is only one copy of it If such a variable is changed by a recursive function it s changed at all levels The various levels interfere with one another This can get very confusing Don t let this happen to you 20 Don t look down When you write or debug a recursive function think about this level only Wherever there is a recursive call assume that it works correctly If you can get this level correct you will automatically get all levels correct You really can t understand more than one level at a time so don t even try 21 member again boolean member X L if L is the empty list return false This says if list L is empty then X isn t an element of L Is this a true statement if X equals the first element in L return true This says if X the first element in L then it s in L Is this a true statement return member X L first element This says if X isn t the first element of L then X is in L if and only if X is in the tail of L Is this a true statement Did we cover all possible cases Did we recur only with simpler cases Did we change any non local variables We re done 22 Reprise Do the base cases first Recur only with a …
View Full Document
Unlocking...