6. RecursionRecursion in the non-computer worldDeveloping a Recursive SolutionStacking/Unstacking Recursive CallsRecursion PitfallsRecursive Function with two ParametersRecursive ProceduresNumber-based vs List-based RecursionStream- based recursionEnumeration-based RecursionIndex-based RecursionVar ++ vs. ++ VarSingle assignment in function callsCommon aspects of list-based recursionRecursion vs. Loops and StacksPrint an object arrayTreesTree-based recursionTracing tree-based recursionIndirect RecursionInstance Method Recursion and TracesVisiting/Traversing Tree NodesRecursively Creating a TreeComposite Design PatternComposite Pattern in ToolkitsGrammars and structure-based RecursionSummaryExercisesRecursionCOMP 114 Prasun Dewan1 6. RecursionLoops are one mechanism for making a program execute a statement a variable number of times. Recursion offers an alternative mechanism, considered by many to be more elegant and intuitive. It is the primary mechanism for repeating execution in some languages. The repetition is achieved, not by using some special new kind statement, but by simply making a method call itself.Recursion in the non-computer worldThis concept is not restricted to the computer world. Words in dictionaries are often defined, directly or indirectly, in terms of themselves. If you look up the Oxford dictionary, “adequate” is defined as “satisfactory,” and vice versa. One can imagine defining “recursion” as “recursion” to illustrate the concept in a very direct manner! The Oxford dictionary actually defines this word as an “expression giving successive terms of a series,’’ pointing out the use of recursion in Mathematics. In fact, as we will see here, we many of the recursive methods we will implement simply encode mathematical definitions of various kinds of number series. The Webster dictionary defines it as a “procedure repeating itself indefinitely or untilcondition met, such as grammar rule”. Let us look at grammar rules in some depth, as they are the foundation of many computer science concepts you will study in future courses, and perhaps best illustrate the kind of recursion on which we will focus here.Consider noun phrases such as:boylittle boysmart little boynaughty smart little boyWe can see here a systematic way of creating noun phrases. A noun phrase can be a noun such as a “boy”. Orit an be an adjective such as “little” followed by a noun phrase. Thus, we have recursively defined a noun phrase in terms of itself. This is illustrated more formally in the following definitions:<Noun Phrase>  <Noun><Noun Phrase>  <Adjective> <Noun Phrase>The terms within angle brackets are called non-terminals. These don’t actually appear in sentence fragments we are describing. The components of sentence fragments such as “smart” and “boy” are called terminals. Think of non-terminals as types such as int and String and think of terminals as values of these types such as3 and “hello”. The matching of terminals such as boy with corresponding non terminals such as nouns is described outside the grammar.Each of the above rules describes a non-terminal on the left hand side in terms of non-terminals and terminals on the right hand side. There may be more than one rule describing the same non-terminal. In fact, when one of the rules is recursive, such as the second rule above, there must be another non-recursive rule toensure the derivation process halts. Alternative definitions of the same non-terminal will correspond to use of conditionals in the recursive methods we will see. 1  Copyright Prasun Dewan, 2000. 1RecursionLet us see how different sentence fragments can be recognized by the rules above. Consider the fragment “boy”. Figure 1 (a) shows how it can be derived from the rules above. Similarly, Figure 1 (b), (c), and (d) show how the sentence fragments “little boy,” and “smart litlle boy” are derived from these rules. boy<Noun Phrase><Noun> <Noun Phrase>boy<Adjective><Noun Phrase><Noun>little<Noun Phrase>boy<Adjective><Noun Phrase><Noun>little<Adjective>smart<Noun Phrase> (a) Deriving “boy” (b) Deriving “little boy” (c) Deriving “smart little boy”Figure 1 Deriving various noun phrases from the rules above The process of writing recursive methods will follow a similar structure, as we see below.Developing a Recursive SolutionTo illustrate the nature of recursion, consider the function, factorial(), which takes as an argument a positive integer parameter, n, and returns the product of the first n positive integers. We can solve this problem using iteration (loops). Here we will develop a recursive solution to it.Before we look at the steps of the function, let us look at what this function computes for different values, n. factorial (0) = 12 factorial (1) = 1 = 1 * factorial (0)factorial (2) = 2 * 1 = 2 * factorial (1) factorial (3) = 3 * 2 * 1 = 3 * factorial (2) Based on the pattern in these examples, we can say:factorial (n) = 0 if n == 0 factorial (n) = n *sum (n - 1) if n > 0What we have above, in fact, is a precise definition of the problem we must solve. As it turns out, it also gives us an algorithm for solving the problem:public static int factorial (int n) { if (n == 0) return 1; if (n > 0) return n*factorial(n-1);}Figure 2 Recursive FactorialIf we were to try and compile this method, the compiler would complain, saying that the function does not return a value. This is because we have not covered all possible values of n. We are assuming here that n is a2 It is not clear what the product of the first 0 positive integers is. The convention is to assume it is 1.2Recursionpositive integer. Though that is the expected value, Java will not prevent a negative integer to be passed as an actual argument. Therefore, we must specify what value should be returned in this case. Let us return the factorial of the absolute value of n, for negative values of n:public static int factorial (int n) { if (n == 0)return 1;else if (n < 0) return factorial (-n); else return n*factorial(n-1);}A method such as factorial that calls itself is called a recursive method.Notice how compact our recursive solution is. It can be considered more elegant than the iterative solution because the algorithm for the problem is also the definition of the problem! As a result, it is easy to convinceourselves that our solution meets the requirements laid out by the definition, and we do need to