RecursionDefinitions IDefinitions IIRecursive functions...er, methodsAnatomy of a recursionInfinite recursionAnother problemWhy recursion?Understanding recursionBase cases and recursive casesInformation hidingStepping through called functionsWe have small headsThe four rulesDo the base cases firstRecur only with a simpler caseExample 1: memberExample 2: doubleIt's OK to modify local variablesIt's bad to modify objectsDon't look downMEMBER againRepriseThe EndJan 13, 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 call6Infinite recursionThe 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 methods7Another problemConsider 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 nonlocal variable makes the program much more difficult to understand8Why 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 loopFor working with inherently recursive data, such as arithmetic expressions, recursion is much simplerExample: To evaluate the expression (2 + 3) * (4 + 5), you must first evaluate the expressions (2 + 3) and (4 + 5)Recall the definition of a list: A list consists of:An open parenthesis, "("Zero or more atoms or lists, andA close parenthesis, ")"Lists are also inherently recursive9Understanding recursionThe usual way to teach recursion is to “trace through” a recursion, seeing what it does at each levelThis may be a good way to understand how recursion works......but it's a terrible way to try to use recursionThere is a better way10Base 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 problem11Information hidingfunction 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?12Stepping through called functionsFunctions should do something simple and understandableWhen you try to understand a function, you should not have to step through the code of the functions that it callsWhen you try to understand a recursive function, you should not have to step through the code of the functions it calls13We have small headsIt's hard enough to understand one level of one function at a timeIt's almost impossible to keep track of many levels of the same function all at onceBut you can understand one level of one function at a time......and that's all you need to understand in order to use recursion well14The four rulesDo the base cases firstRecur only with a simpler caseDon't modify nonlocal variables*Don't look down * Remember, parameters count as local variables15Do 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 firstThis is just writing ordinary, nonrecursive code16Recur 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”17Example 1: memberIs 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}18Example 2: doubleDouble 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 }}19It's OK to modify local variablesA function has its own copy of local variablesparameters passed by value (which are effectively local variables)Each level of a recursive function has its own copy of these variables and parametersChanging them at one level does not change them at other levelsOne level can't interfere with another level20It's bad to modify objectsThere is (typically) only one copy of a given objectIf a parameter is passed by reference, there is only one copy of itIf such a variable is changed by a recursive function, it's changed at all levelsThe various levels interfere with one anotherThis can get very confusingDon't let this happen to you!21Don't look downWhen you write or debug a recursive function, think about this level onlyWherever there is a recursive call, assume that it works
View Full Document
Unlocking...