Recursion COMP 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 1 Recursion Let 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 Noun Phrase Noun Phrase smart Noun Phrase Adjective Noun little boy a Deriving boy Adjective Noun Phrase Noun Phrase Adjective Noun little boy b Deriving little boy Noun Phrase Noun 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 2 Recursion If 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 offby 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 integer is reduced to the problem of computing the factorial of its positive absolute value 2 Base Terminating Case s It has terminating condition s indicating how the base case s that is the smallest size problem s can be solved In the example it tells us that factorial 0 1 In general there can be more than one base case for instance one for negative numbers and another for 0 Once we define the problem in this way we can use recursion to