ale. if aso ala a * (8 — 3) s (a = Byee he Ledges fh The three dots are really a shorthand for all the numbers between n — 3 and 2 multiplied together. To avoid this shorthand in the definition of n!_we would have to list a formula for n! for each value of n separately, as follows: Olea wad 21-2 Beg zi Of course, we cannot hope to list a formula for the factorial of each integer. To avoid any shorthand and to avoid an infinite set of definitions, yet to define the function precisely, we may present an algorithm that accepts an integer n and returns the value of n!. prod = 1; Fetara(prod); Such an algorithm is called iterative because it cals forthe explicit repetition of some process until a certain condition is met. This algorithm can be translate readily into a C function that returns n! when n is input as a parameter. n alge ‘may be thought of as a program for an “ideal” machine without any limitations of a real computer and may therefore be used to define a function. A C function, however, cannot serve as the math factorial function because of such limitations as precision and real machine. Let us look more closely at the definition of n! that, for each value of n. We may note, for example, that which equals 4 + 31. In fact, for any n > 0, we see th Multiplying n by the product of all i all integers from n to 1. We may o: uw or 2!of= 2) if nae al=n* (n-1)) if a > 0. This definition may appear quite strange, since it defines the factorial function in terms of itself. This seems to be a circular definition and totally unacceptable until we realize that the mathematical notation is only a concise way of writing out the infinite number of equations necessary to define n! for each n. 0! is defined directly as 1. Once 0! has been defined, defining 1! as 1 * 0! is not circular at all. Similarly, once 1! has been defined, defining 2! as 2 « 1! is equally straightforward. It may ‘be argued that the latter notation is more precise than the definition of n! as n« (n~ 1) *-+-« 1 for n > 0 because it does not resort to three dots to be filled hoped) logical in of the reader. Such a definition, which-defines Let us see how the recursive definition of the factorial function may be used evaluate 5!. The definition states that 51 equals 5 » 4!. Thus, before we can . we must fist evaluate 41. Using the definition once more, we Repeating, this procesThis algorithm exhibits the process used to compute n! by the recursive definition. The key to the algorithm is, of course, line 5, where we are told to “find the value of x1,” This requires reexecuting the algorithm with input x, since the method for computing the factorial function is the algorithm itself. To see that the algorithm eventually halts, note that at the start of line 5, x equals n — 1. Each time the algorithm is executed, its input is one less than the preceding time, so that (since the original input n was a nonnegative integer) 0 is eventually input to the algorithm. At that point, the algorithm simply returns 1. This value is returned to line 5, which asked for the evaluation of 0!. The multiplication of y (which equals 1) by n (which equals 1) is then executed and the result is returned. This sequence of multiplications and retums continues until the original n! has been evaluated. In the next section we will see how to convert this algorithm into a C program. Of course, it is much simpler and more straightforward to use the iterative method for evaluation of the factorial function. We present the recursive method as a simple example to introduce recursion, not as a more effective method of solving this particular problem. Indeed, all the problems in this section can be solved more efficiently by iteration. However, later in this chapter and in subsequent chapters, we will come across examples that are more easily solved by recursive methods. ‘Muttiplication of Natural Numbers Another example of a recursive definition is th natural numbers. The product a + B, w b defined as a added to itself b recursive definition isor a*bea* (b+) -a we would be unable to determine the value of 5! or 6 + 3. (You are invited to attempt to determine these values using the foregoing definitions.) This is true despite the fact that the two equations are valid. Continually adding one to n or b does not eventually produce an explicitly defined case. Even if 100! was defined explicitly, how could the value of 101! be determined? ‘The Fibonacci Sequence Let us examine a less familiar example. The Fibonacci sequence is the sequence of integers 0, Lyi Ay 2503, 5). 8p) 1359215934) oe Each element in this sequence is the sum of the two preceding elements (for example, O+1=1,1+1=2,14+2=3,2+3=5,...). If we let fib(0)=0, fb(1)=1, and so on, then we may define the Fibonacci sequence by the following recursive definition: fib(n) = 2 if a == 0 or a == 1 fib(n) = fib(n - 2) + fib(n - 1) if a >= 2 To compute fib(6), for example, we may apply the definition recursively to obtain fib(b) = £1b(4) + fib(S) = fib(2) + fib(3) + £ib(S) = £ib(0) + fib(1) + fib(3) + fib(5) = O + 1 + £ib(3) + £4b(S) = 4 + fib(l) + fib(2) + £1b(S) = 1 + f1b(0) + fib(1) + £ib(S) = O+ 2+ £4b(5) = 3 + fib(3) + Fid(4) = fib(1) + £ib(2) + £1b(4) = + f1b(D) + £ib(1) + £ib(4) = + 1+ £1b(2) + £1b(3) = S + £id(0) + he? Bea ae (oa eciotog 7 cha ae wenuune Baer ey ey coo the recursive definitions of the factorial function and multiplican i definition of fib refers to itself twice. For example, fib(6) = Pole) + aS), Sra computing fb~6), flo must be applied recursively twice. However, the computation of fl(3) also involves determining fib4), so that a great deal of computat redundancy occurs in applying the . In the foregoing example, fib(3) is the value of fib(3) the first time that it is evaluated and reuse it each time that it bakes Sneiae boa of computing b(n) such as the following is much Z eeif (n @ 4) return(n); lofib = 0; hifib = 1; for (i= 2; 4 <= a; itt) { x = lofid; ofib = hifid; hifib = x + lofib; } /* ena for */ retura(hifib); Compare the number of additions (not including increments of the index vari- able #) that are performed in computing fid(6) by this algorithm and by using the recursive definition. In the case of the factorial function, the same number of multi- plications must be performed in computing n! by the recursive and iterative methods. ‘The same is true of the number of additions in the two methods of computing multiplication, However, in the case of the Fibonacci numbers, the recursive method is far more expensive than the iterative. We shall have more to say about the relative merits of the two methods in a later section. The Binary Search You may have received the erroneous impression that recursion is a very handy ‘ool for defining mathematical functions but has no influence in more practi computing activities. The next example illustrates an application of recursi of the most common activities in computing: that of searching. = Consider an array of elements in which objects have been order. For example, a dictionary or telephone book may be tho whose entries are in alphabetical order. A company payroll file of employees’ social security numbers. Suppose that such i in it, For example, we and compared with the item being searched unordered and haphazardly constructed, the find anything in it (unless, of cours 4 method would never be used in 1o«search process is repeated in the first half of the array (since if the item appears anywhere it must appear in the first half); otherwise, the process is repeated in the second half. Note that each time a comparison is made, the number of elements yet to be searched is cut in half. For large arrays, this method is superior to the sequential search in which each comparison reduces the number of elements yet to be searched by only one. Because of the division of the array to be searched into ‘two equal parts, this search method is called the binary search. Notice that we have quite naturally defined a binary search recursively. If the item being searched for is not equal to the middle element of the array, the instructions are to search a subarray using the same method. Thus the search method is defined in terms of itself with a smaller array as input. We are sure that the process will terminate because the input arrays become smaller and smaller, and the search of a one-element array is defined nonrecursively, since the middle element of such an array is its only element. : We now present a recursive algorithm to search a sorted array a for an element x between a{low] and a{high]. The algorithm retums an index of a such that nde ‘equals x if such an index exists between low and high. If x is not found in that p tion of the array, binsrch retums —1 (in C, no element a[—1] can exi Dy, Tee 1 if (low > high) 1 2 return,line 1: Is 4 > 7? No, so execute line a line 3: mid = (4 + 72 = S$. line 4: Is x == a[5]? 17 does not equal 18, so execute line 6. line 6: Is x < a[S}? Yes, since 17 < 18, so search for x in a{low] to a{mid — 1). line 7: Repeat the algorithm with low = low = 4 and high = mid - 1 = 4, ‘We have isolated x between the fourth and the fourth elements of a. line I: Is 4 > 4? No, so execute line 3. line 3: mid = (4 + 4)/2 = 4, line 4: Since a[4] 17, return mid = 4 as the answer. 17 is indeed the fourth element of the array. Note the pattem of calls to and retums from the algorithm. A diagram tracing {his pattem appears in Figure 3.1.1. The solid arrows indicate the flow of control through the algorithm and the recursive calls. The dotted lines indicate retums. Since there are no steps to be executed in the algorithm after line 7 or 9, the retuned result is retumed intact to the previous execution. Finally, when control returns to the original execution, the answer is retumed to the caller. ‘ Let us examine how the algorithm searches for an item in the array. Assume the array a as in the previous exam searching for x, which equals 2. oi line 1 Is low > high? 0 Tine 3: mid = (0 + 7)/2 = 3. line 4: Is [3]?line 7: Repeat the algorithm with low = low = O and high = mid ~ | = 2 If2 appears in the array, it must appear between a{0] and a2} inclusive, line 1: Is 0 > 22 No, execute line 3. line 3: mid = (0 + 22 = 1. line 4: Is 2 == a{1}? No, execute line 6. line 6:1s 2 < afi}? Yes, since 2 <3. Search for x in a{low] to almid ~ 1), Jine 7: Repeat the algorithm with low = low = 0 and high = mid — 1 = If x exists in a it must be the first element. line 1: Is 0 > 0? No, execute line 3. line 3: mid = (0 + Oy2 = 0. line 4: Is 2 == a0]? No, execute line 6. line 6: Is 2 < a[0]? 2 is not less than 1, so perform the else clause at line 8, line 9: Repeat the algorithm with low = mid +1 = 1 and high = high =0, line 1: 1s low > high? 2 is greater than 1, so ~1 is returned. The item 2 does not exist in the array. Properties of Recursive Definitions or Algorithms Let us summarize what is involved in a recursive definition or algorithm. One imporiant requirement for a recursive algorithm to be correct is that it not generate ‘an infinite sequence of calls on itself. Cleariy, any algorithm that does generate such _ 3 Seahence can never terminate. For at least one argument or group of arguments, inctio be defined in terms that do not involve f. There must besuce(x) int x; { retara(x++); } 7* end suce */ 3.1.3. Let a be an array of integers. Present recursive algorithms to compute the maximum element of the array . the minimum element of the array ¢. the sum of the elements of the array 4. the product of the elements of the array €, the average of the elements of the array 3.1.4. Evaluate each of the following, using both the iterative and recursive definitions: a. 6! | b. 9! e100 +3 | a. 644 e. fb(10) f. foc) 3.1.5. Assume that an array of ten integers contains the elements 1, 3, 7, 15, 21, 22, 36, 78, 95. 106 Use the recursive binary search to find each of the following items in the array sai ;3 The recursive algorithm to compute n! may be directly translated into a c function as follows: fact(n) int n; int x, y; if (n == 0) return(1); X= 1-3; Y = fact(x); retura(n * y); } /* end fact */ In the statement y = fact(x); the function fact calls itself. This is the essential Rerstient of @ recursive routine, The programmer assumes that the function being computed has already been written and uses it in its own definition. However, the Programmer must ensure that this does not lead to an endless series of calls. Let us examine the execution of this function when it is called by another Program. For example, suppose thatthe calling program contains the statemenr Print£("za", fact(<)); Sowisenernis is: ee teaEen Figure 3.2.1 contains a series of snapshots of the stacks for the variables n, %, and y as execution of the fact function proceeds. Initially, the stacks are empty, as illustrated by Figure 3.2.12. After the first call on fact by the calling procedure, the situation is as shown in Figure 3.2.1b, with n equal to 4. The variables x and y are allocated but not initialized. Since n does not equal 0, x is set to 3 and fac) is called (Figure 3.2.1c). The new value of n does not equal 0; therefore x is set to 2 and fact(2) is called (Figure 3.2.14). ‘This continues until n equals 0 (Figure 3.2.1f). At that point the value 1 is returned from the call to facr(0). Execution resumes from the point at which facr(0) Was called, which is the assignment of the retumed value to the copy of y declared in fact(1). This is illustrated by the status of the stack shown in Figure 3.2.1g, where the variables allocated for fact(0) have been freed and y is set to 1. ‘The statement rerurn(n * y) is then executed, multiplying the top values of n and y to obtain | and retuming this value to fact(2) (Figure 3.2.1h). This process is A LL iD, (ay CUnitaty), (6) fact (4). ———_(e) fact (3).repeated twice more, until finally the value of y in fact(4) equals 6 (Figure 3.2.1), The statement return(n + y) is executed one more time. The product 24 is retuned to the calling procedure where it is printed by the statement printf("Sa", fact(4)); Note that each time that a recursive routine retums, it returns to the point immediately following the point from which it was called. Thus, the recursive cal] to fact(3) retums to the assignment of the result to y within facr(4), but the recursive call to fact(4) retums to the pringf statement in the calling routine. Let us transform some of the other recursive definitions and processes of the previous section into recursive C programs. It is difficult to conceive of a C pro- ‘grammer writing a function to compute the product of two positive integers in terms of addition, since an asterisk performs the multiplication directly. Nevertheless, such a function can serve as another illustration of recursion in C. Following closely the definition of multiplication in the previous section, we may write: mult(a, b) int a, bjif (b == 2) return(a); © = b-1; a = mult(a, c); sum = d4a; return(sum); } /* end malt */ Another point that should be made is that it is particularly important to check for i jput parameters in a recursive routine. For example, let us examine the execution of the fact function when it is invoked by a statement such as print£("\nza", fact(-1)); Of course, the facr function is not designed to produce a meaningful result for negative input. However, one of the most important things for a programmer to Jeam is that a function invariably will be presented at some time with invalid input and, unless provision is made for such input, the resultant error may be very difficult to trace. For example, when ~1 is passed as a parameter to fact, so that n equals ~1, xis set to ~2 and ~2 is passed to a recursive call on fact. Another set of n, x, and ¥ is allocated, n is set to —2, and x becomes ~3. This process continues until the Program either runs out of time or space or the value of x becc small.- ‘The Fibonacci Numbers in C ‘We now turn our attention to the Fibonacci sequence. A C program to compute the nth Fibonacci number can be modeled closely after the recursive definition: fib(n) ant n; j { ant x, y5 if (n <= 1) retora(n x = fib(n-3); y = fib(n-2); return(x + y); } /* end fib */ Let us trace through the action of this function in computing the sixth Fibonacci ‘number. You may compare the action of the routine with the manual computation we performed in the last section to compute (6). The stacking process is illustrated in Figure 3.2.2. When the program is first called, the variables n, x, and y are allocated, and n is set 10.6 (Fig. 3.2.22). Since n > 1, n ~ 1 is evaluated and fib is recursively. A new set of n, x, and y is allocated, and n is set to 5 (Fig.a5 eer ieee. -2.. |S ce eee a Ee este =—-s—- eos. eee tae * Pea o es. = * eee] S ee meee = x 24 ees os = ne Eee * «|e Sue ee le © © a ee eesHowever, in looking at the binary search algorithm of Section 3.1 as a model for a recursive C routine, we note that two other parameters are passed in the recursive calls. Lines 7 and 9 of that algorithm call for a binary search on only part of the array. Thus, for the function to be recursive the bounds between which the array ig to be searched must also be specified. The routine is written as follows: binsrch(a, x, low, high) int aC]; int x; ant high, low; { aint mid; if (low > high) return(-1); mid = (low + high) / 2; return(x == a(mid) ? mid : x < almia] 2? binsrch(a, x, low, mid-1) binsrch(a, x, mid+l, high)) } /™ end binsrch */ __ When binsrch is first called from another routine to search for x in an array