Recursion 1COMP 401 Prasun Dewan1 25. Recursion Loops 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 world This 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 until condition 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: boy little boy smart little boy naughty smart little boy We can see here a systematic way of creating noun phrases. A noun phrase can be a noun such as a “boy”. Or it 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 as 3 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 to ensure 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.Recursion 2Let 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 Solution To 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 > 0 What 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 Factorial 2 It is not clear what the product of the first 0 positive integers is. The convention is to assume it is 1.Recursion 3If 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 a positive 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 convince ourselves that our solution meets the requirements laid out by the definition, and we do need to risk the off-by-one errors of loop iteration. The key to using recursion is to identify a definition that meets the following two requirements: 1. Recursive Reduction Step(s): It defines the result of solving a larger problem in terms of the results of one or more smaller problems. A problem is considered smaller than another problem if we can solve the former without having to solve the latter. In our example, the problem of computing the factorial of positive n is reduced to the problem of computing the factorial of a smaller number, n-1; and the problem of computing the factorial of a negative