Chapter 15 Recursion / 1

Chapter 15Recursion

Objectives

After reading this chapter you will be able to:

  • Develop an understanding and appreciation about the concept of recursion.
  • Know the difference between recursion and iteration.
  • Write recursive definitions.
  • Determine when to use recursion instead of iteration.
  • Develop and appreciate the trade-offs between recursion and iteration.

Introduction

In Chapter 7 we learned about iteration, where a statement or a block of statements repeats a number of times – either by using the while statement, the do/while statement, or the for statement. In this chapter you will learn about another type of programming technique that causes, not only a statement or a block of statements to be executed, but the entire method is called to repeat itself.

The concept of recursion can be seen all around us. When the reflective surfaces of two mirrors are placed parallel to each other, they form an endless series of images. In this situation, one mirror calls upon the other to produce the image it sees, likewise the other mirror. Consider the song:

This song by definition is recursive, since it is made to repeat word for word, except the count of the number of green bottles, and the last line that ends it.

Whereas in the first case the process seems not to end, it the second it does end. In programming we prefer the recursive definition that has a finite number of calls – hence the recursion must end.

Recursion

Recursion is a process that repeats itself a finite number of times, until a given condition is met, then the process stops. The desired result from the process is realized only when the continuous call stops. The condition that causes the process to terminate is referred to as the base case, and the condition for the continuous call is referred to as the inductive step. The inductive step specifies the set of rules that causes the process to move towards the base case.

The bottle song above can be modeled as a recursive definition, as shown the flowchart of Figure 15.1.

To understand how recursion works, it is useful to visualize what happens when a recursive definition is invoked. Let us consider the Mathematical concept called factorial, written n!. By definition:

This is read:

n factorial = 1, if n is zero;

Otherwise it is, n times the factorial of (n – 1). This occurs when n > 0.

Example 15.1 Find the value of 4!

According to the definition of factorial, inductive step, produces three factors:

  1. The number for that factorial
  2. The operator that is involved (in this case the operator is multiplication), and
  3. The call to repeat the process (which in this case is factorial (n - 1).

Figure 15.2 shows a trace of 4! The algorithm actually asks if the number for which it wants to find the factorial is zero. If this is the case then the base case has been reached, and the value that is to be generated and stored must is 1. If the number is not zero, then this forms the basis for the inductive step, in which case the production generates the three terms as shown in Figure 15.2.

Once the base case has been reached, it is time for the actual multiplication to take place. The way that this works is as follows. Starting with the last value that was generated, by the base case, this value gets multiplied by its predecessor, and its predecessor, all the way back to the first value that was generated. In the end, the value (24 in this case) is generated. See Figure 15.3.

Although this process looks complicated, the programming is very simple. One of the first things to recognize when dealing with recursion is that the principle is based on the selection construct if/else. The only stipulation in the test is to first ascertain if the base case has been reached. If it has been reached, the result will automatically be generated. If not, the process is called again.

Revisiting the factorial problem, n! can be expressed as a method definition as follows:

The above algorithm converted to program is shown in Listing 15.1. Notice that the method definition follows exactly as the algorithm.The effect of thisalgorithmis:

factorial(4) =

4 * factorial(3)

4 * (3 * factorial(2))

4 * (3 * (2 * factorial(1)))

4 * (3 * (2 * (1 * factorial(0))))

4 * (3 * (2 * (1 * (1)))))

Once the base case is reached, the actual multiplication is performed, starting with the last value down to the first, as shown below.

4 * (3 * (2 * (1 * (1))))

= 4 * (3 * (2 * ( 1 ) ) )

= 4 * ( 3 * ( 2 ) )

= 4 * ( 6 )

= 24

Listing 15.1shows the class called Recursion with the single method called factorial that evaluates n!.

Listing 15.2 shows a typical test class called TestRecursion.

Example 15.2Find the value of Σn!

Solution

By definition, Σn! = n! + Σ(n – 1)! , n ε Integer, n > 0

This expression at first looks intimidating, but we know that

Therefore this solution is simplified to be:

The above algorithm is easily coded as a recursive construct, as shown in Listing 15.3.

It is known that multiplication is nothing more than repeated addition. Although easily said, it may not be that easy to prove, unless it is by recursion.

Example 3. Given two positive integers, a and b, a recursive definition can be expressed as follows:

This definition, like the factorial definition is easily coded in its natural form, as shown in

Listing 15.4.

Searching a Sorted List

In chapter 9 we studied the binary search algorithm using iteration. Recall that the algorithm requires that the list must first be sorted. In conducting the search, the list must be partitioned into three – the midpoint of the list, and the two sub list, one on either side of the mid-point. See Figure 15.6. Let’s say we are searching for the value 45. In the figure you will see that this value is not at the midpoint. In addition, we see that it lies to the right of the mid-point.

[0] / [1] / [2] / [3] / [4] / [5] / [6] / [7] / [8] / [9]
5 / 7 / 16 / 24 / 25 / 30 / 45 / 50 / 62 / 65

Figure 15.7

The second time around the new sub list is right of the midpoint – that is, index 5 thru 9. Hence, the new mid-point is calculated in similar manner to the previous. See Figure 15.7.

Figure 15.8

[0] / [1] / [2] / [3] / [4] / [5] / [6] / [7] / [8] / [9]
5 / 7 / 16 / 24 / 25 / 30 / 45 / 50 / 62 / 65

From this analysis, see that the process consists of one of four outcomes – the items is found at the mid-point of a sub list; the item is not found at all; the process of finding the mid-point on the left; or finding the midpoint to the right. As we see in Listing 15.7 this algorithm lends itself to recursion.

Searching a Non-Sorted List

Just a recursion can be used to search sorted list, it can also be used to search unsorted lists. For instance, if we want to search a piece of text for a given string, we would first tokenize the string using class such as StringTokenizer. Once the text is tokenized, there three possible outcomes – the string is locate, the string is not locate, or call the method again, and again. Each time that the method is called, the remaining portion of the text is searched. Listing 15.8 shows a recursive method that searches a piece of text for a given string. In addition to finding the text, it also finds the position in the text where it is found. This value is represented by the variable, index.

Recursion vs Iteration – Which Approach Is Better

Recursion and iteration perform the same kinds of tasks - they repeat segments of codes in order to solve a problem.Although there are no clear answers to which is better, there are however, known trade-offs between, the execution times of both approaches; the amount of memory each uses; and in general the level of difficulty in the programming.

Execution Time

Let us use the problem of finding Σn! to help us understand the time difference of both approaches. Listing 15.4 shows the code for both recursion and iteration. The method sumFactorial (Lines 11 thru 17) shows the recursive definition for Σn!The method also calls the recursive definition for n!, which is needed in the process. See Lines 3 thru 9.

Listing 15.4 Recursive and iterative definition for finding Σn!
  1. class Recursion
  2. {
  3. long factorial(int n)
  4. {
  5. if ( n == 0 )
  6. return 1;
  7. else
  8. return n * factorial(n - 1);
  9. }
  10. long sumFactorial(int n)
  11. {
  12. if (n == 0)
  13. return 1;
  14. else
  15. return factorial(n) + sumFactorial(n-1);
  16. }
  17. long findFactorial(int n)
  18. {
  19. long product = 1;
  20. for (int i = 1; i <= n; i++)
  21. product = product * i;
  22. return product ;
  23. }
  24. long sumTheFactorials(int n)
  25. {
  26. long sum = 0;
  27. for (int i = 1; i <= n; i++)
  28. sum = sum + findFactorial(i);
  29. return sum + 1;
  30. }
  31. }

Similarly, Lines 28 thru 35 shows the iterative method definition for finding Σn! Also, Lines 19 thru 26 defines n! This as you know is needed in the process.

The test class shown in Listing 15.5 calls both the recursive and the iterative procedures. In each case the calls are timed. The for loop in each case produces the value n, for which the value of Σn! is calculated.

Figure 15.4 shows a sample output for Σn! These values may change slightly, each time that the program is executed. Nevertheless, the result will show that the recursive approach will always take more time to process than the iterative approach.

If we pick any pair of points representing recursion, and a corresponding pair of points representing iteration, we find that recursion spends much more time processing the codethan iteration. For example, using Figure 5.4, let us choose points, P1 (2, 3) and P2(4, 9), for recursion. The slope m1, representing these points is:

m1 = (9 – 3)/(4 – 2) = 6/2

Now choose corresponding iteration points Q1(2, 3) and Q2 (4, 4), representing iteration. The slope m2, representing these points is:

m2 = (4 – 3)/(4 – 2) = 1/2

This analysis shows that the rate m1: m2 ≈ 6:1. This means that recursion takes about 6 times the time it takes to loop through the solution than iteration.

Figure 15.4
Execution Timing (Units of time)
n / Recursion / Iteration / Σn!
1 / 17 / 13 / 2
2 / 3 / 3 / 4
3 / 7 / 4 / 10
4 / 9 / 4 / 34
5 / 11 / 5 / 154
6 / 14 / 6 / 874
7 / 17 / 6 / 5914
8 / 22 / 7 / 46234
9 / 25 / 9 / 409114
10 / 31 / 9 / 4037914
11 / 37 / 11 / 43954714
12 / 41 / 12 / 522956314
13 / 51 / 14 / 6749977114
14 / 59 / 18 / 93928268314
15 / 63 / 20 / 1401602636314

The graph of this table is shown in Figure 5.5. The graph shows, apart from the first value, two approximately linear mappings – recursion vs. iteration. As you can see, the graph for the recursion quickly outgrows the graph for iteration.

Memory Usage

As you haveseen the amount of time spent on a recursive definition, is dependent on the number of times the method calls itself. Much of this time is spent allocating memory to store the partial results after each call. The shaded cells of Figure 15.6 shows that additional memory is needed to store at least the multiplicand of the factorial after each call.

With the iterative approach,Listing 15.5shows that only three chunks of memory are required, one for each of the variables –n, product, and i.This is true, no matter the number of iterations. That is, memory usage is constant. Using 4!as an example, the amount of memory required for iteration is three units; this is because the variables are re-used. If we use 20!, the amount of memory used remains the same.

When it comes to recursion, the amount of memory required depends on the number of times that the method calls itself. In the case of 4! at least thirteen units of memory is required –three units for each time that the method calls itself, and one for the base case.Listing 15.6 shows the method for finding factorial.

Analyzing the code, factorial(4) would cause the method to be called four times. Figure 15.6 illustrates what happens when factorial(4) is called.

Note, if n grows exceedingly large the recursive definition may become unusable for the given problem.

Programming Level of Difficulty

When it comes to the program code, very often programmers preferrecursionoveriteration. In the case of recursion the solutions are often shorter and closer to the conceptual abstraction. Although the programs are generally shorter and more incline to resemble the problem, this approach comes with a price. That is, an algorithm that can naturally be expressed iteratively may not be as easy to understand if expressed recursively. In general, recursion is difficult to understand in some algorithms; also, good recursive solutions maybe more difficult to design and test.

Just like recursion, an algorithm that can naturally be expressed recursively may not be as easy to understand if expressed iteratively. It can also be difficult to convert a recursive algorithm into an iterative algorithm, and verifying that the algorithms are equivalent can also be difficult. In Listing 15.8 compares the recursive definition (a) of n! with the iterative definition (b).

When we analyze the two methods we see that the recursive definition is more readily understood than the iterative definition, as the recursive definition is more aligned to the Mathematical definition:

I guess by now you come to realize that one of the reasons why iteration is more readily understood is that recursion predicates itself on the if/else construct. The base case will appear first, followed by the inductive step in the else clause. A recursive definition may have multiple base cases, as well as multiple inductive steps. For example:

Therefore, if we are strictly wanting to carry out the calculation for n! the algorithm could be defined as:

Self-Check

  1. Design a recursive algorithm that evaluates xn, where n is a positive integer.
  1. Define an iterative method and a recursive method that take parameters x and n and evaluate xn. Which of the two approaches was easier to code? Explain.
  1. Using the algorithm below, write an iterative definition and a recursive definition that compute the greatest common divisor (gcd) of two integers. The gcd of two integers is the largest integer that divides them both.

Compare codes and say which definition was easy to write.

Chapter Summary

  • Use recursion for clarity, and (sometimes) for a reduction in the time needed to write and debug code, not for space savings or speed of execution.
  • Every recursive definition must have a base case; otherwise the recursive process will be an infinite loop.
  • Every recursive definition must make progress towards its base case; otherwise this too will be an infinite loop.
  • Sometimes a recursive method has more than one base case, and also more that one inductive steps.
  • Recursion has large memory usage and time consumption overheads. This takes O(2n) steps in general to solve ! Unusable for large n.