DOC PREVIEW
Penn CIT 594 - Recursion

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Recursion Jan 14 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 Another dumb example The following fills an array with the numbers 0 through n 1 void run int a new int 10 fill a a length 1 System out println Arrays toString a void fill int a int n if n 0 return else a n n fill a n 1 0 1 2 3 4 5 6 7 8 9 6 Parts of the dumb example Base case does some work without making a recursive call void fill int a int n if n 0 return Recursive case else recurs with a a n n simpler parameter fill a n 1 Extra work to convert the result of the recursive call into the result of this call 7 Improving the dumb example The line fill a a length 1 just seems ugly Why should we have ask the array how big it is then tell the method Why can t the method itself ask the array Solution Put a front end on the method like so void fill int a fill a a length 1 Now in our run method we can just say fill a We can if we want hide the two parameter version by making it private 8 The four rules Do the base cases first Recur only with simpler cases Don t modify and use non local variables You can modify them or use them just not both Remember parameters count as local variables but if a parameter is a reference to an object only the reference is local not the referenced object Don t look down 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 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 The important part here is testing before you recur the actual work can be done in any order long factorial long n if n 1 return n factorial n 1 else return 1 However it s usually better style to do the base cases first This is just writing ordinary nonrecursive code 11 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 12 Infinite recursion The following is the recursive equivalent of an infinite loop int toInfinityAndBeyond int x return toInfinityAndBeyond x This happened because we recurred with the same case While this is obviously foolish infinite recursions can happen by accident in more complex methods int collatz int n if n 1 return 1 if n 2 0 return collatz n 2 else return collatz 3 n 1 13 Don t modify and use non local variables Consider the following code fragment int n 10 int factorial if n 1 return 1 else n n 1 return n 1 factorial It is very difficult to determine without trying it whether this method works The problem is keeping track of the value of n at all the various levels of the recursion 14 Modifying or using global variables When we change the value of a global variable we change it for all levels of the recursion It s okay to modify a global variable if we don t also use it For example we might update a variable count as we step through a list It s okay to use read a global variable if we don t also try to change it Hence we cannot understand a single level in isolation As far as our code is concerned it s just a constant The problem comes when we try to both modify a global variable and use it in the recursion 15 Using non local variables int total 0 int b 1 2 3 4 5 6 7 8 9 10 int sum int n if n 0 return total else total b n sum n 1 return total System out println Total is sum 9 The global array b is being used but not changed The global variable total is being changed but not used at least not in any way that affects program execution This program works and can be understood 16 Style The previous method works but it s terrible style int sum int n if n 0 return total else total b n sum n 1 return total What s b What s total Where do these come from The method just isn t very self contained It might be acceptable if b and total are instance variables describing the state of this object but that seems unlikely Some programmers prefer using getters and setters for all instance variables even within the same class 17 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 18 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 Hence it s acting like …


View Full Document

Penn CIT 594 - Recursion

Documents in this Course
Trees

Trees

17 pages

Searching

Searching

24 pages

Pruning

Pruning

11 pages

Arrays

Arrays

17 pages

Stacks

Stacks

30 pages

Recursion

Recursion

25 pages

Hashing

Hashing

24 pages

Recursion

Recursion

24 pages

Graphs

Graphs

25 pages

Storage

Storage

37 pages

Trees

Trees

21 pages

Arrays

Arrays

24 pages

Hashing

Hashing

24 pages

Recursion

Recursion

25 pages

Graphs

Graphs

23 pages

Graphs

Graphs

25 pages

Stacks

Stacks

25 pages

Quicksort

Quicksort

21 pages

Quicksort

Quicksort

21 pages

Graphs

Graphs

25 pages

Recursion

Recursion

25 pages

Searching

Searching

24 pages

Counting

Counting

20 pages

HTML

HTML

18 pages

Recursion

Recursion

24 pages

Pruning

Pruning

11 pages

Graphs

Graphs

25 pages

Load more
Download Recursion
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Recursion and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Recursion 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?