RecursionDefinitions IDefinitions IIRecursive functions...er, methodsAnatomy of a recursionAnother dumb exampleParts of the dumb exampleImproving the dumb exampleThe four rulesBase cases and recursive casesDo the base cases firstRecur only with a simpler caseInfinite recursionDon’t modify and use non-local variablesOK to modify or use global variablesUsing non-local variablesStyleIt's OK to modify local variablesIt's bad to modify objectsDon't look downWe have small heads*Example: memberProving that member is correctRepriseThe EndJan 14, 2019Recursion2Definitions IA recursive definition is a definition in which the thing being defined occurs as part of its own definitionExample:An atom is a name or a number A list consists of:An open parenthesis, "("Zero or more atoms or lists, andA close parenthesis, ")"3Definitions IIIndirect recursion is when a thing is defined in terms of other things, but those other things are defined in terms of the first thingExample: A list is:An open parenthesis,Zero or more S-expressions, andA close parenthesisAn S-expression is an atom or a list4Recursive functions...er, methodsThe mathematical definition of factorial is:We can define this in Java as:long factorial(long n) { if (n <= 1) return 1; else return n * factorial(n – 1);}This is a recursive function because it calls itselfRecursive functions are completely legal in Java1, if n <= 1n * factorial(n-1) otherwisefactorial(n) is5Anatomy of a recursionlong factorial(long n) { if (n <= 1) return 1; else return n * factorial(n – 1);}Base case: does some work without making a recursive callRecursive case: recurs with a simpler parameterExtra work to convert the result of the recursive call into the result of this call6Another dumb exampleThe following fills an array with the numbers 0 through n-1void 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]7Parts of the dumb examplevoid fill(int[ ] a, int n) { if (n < 0) return; else { a[n] = n; fill(a, n - 1); }}Base case: does some work without making a recursive callRecursive case: recurs with a simpler parameterExtra work to convert the result of the recursive call into the result of this call8Improving the dumb exampleThe line fill(a, a.length - 1); just seems uglyWhy 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 private9The four rulesDo the base cases firstRecur only with simpler casesDon't modify and use non-local variablesYou can modify them or use them, just not bothRemember, 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 down10Base cases and recursive casesEvery valid recursive definition consists of two parts:One or more base cases, where you compute the answer directly, without recursionOne or more recursive cases, where you do part of the work, and recur with a simpler problem11Do the base cases firstEvery recursive function must have some things it can do without recursionThese are the simple, or base, casesTest for these cases, and do them firstThe important part here is testing before you recur; the actual work can be done in any orderlong 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 firstThis is just writing ordinary, nonrecursive code12Recur only with a simpler caseIf 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 problemCombine the results of the recursion and the extra work into a complete solution“Simpler” means “more like a base case”13Infinite recursionThe 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 methodsint collatz(int n) { if (n == 1) return 1; if (n % 2 == 0) return collatz(n / 2); else return collatz(3 * n - 1);}14Don’t modify and use non-local variablesConsider 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 worksThe problem is keeping track of the value of n at all the various levels of the recursion15OK to modify or use global variablesWhen we change the value of a “global” variable, we change it for all levels of the recursionHence, we cannot understand a single level in isolationIt’s okay to modify a global variable if we don’t also use itFor example, we might update a variable count as we step through a listIt’s okay to use (read) a global variable if we don’t also try to change itAs far as our code is concerned, it’s just a constantThe problem comes when we try to both modify a global variable and use it in the recursion16Using non-local variablesint 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 changedThe 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 understood17StyleThe 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
View Full Document
Unlocking...