CS 1302 – Ch 18 – Recursion

These notes cover Sections 18.1-18.5, 18.9-18.10

Section 18.1 – Introduction

  1. A recursive method is one that calls itself. As shown on the right, the recursivePrint method calls itself.
  1. Recursionis a problem solving technique that is a form of repetition; however, no loop is involved – instead, a recursive method is employed.
  1. The method above is not particularly useful, nor is it a good use of recursion. However, it is easy to understand and we use it (and subsequent variations that follow) to understand how recursion works. Later we will examine problems where recursion is a natural and useful problem solving technique.
  1. Example 1 – Consider calling the method above with n=2 as shown below (the name of the method has been shortened to recurPrint). Follow the numbered steps in purple:

Notes about the execution:

  • Obviously the output of this method is:2 1
  • This method recurses in Steps 3 and 5. The term recurse is also referred to as winding, and is used to describe the process of a recursive method calling itself over and over.
  • At Steps 2, 4, and 6 a check is made to see if the recursion should continue. This check is called a stopping rule. A recursive method must have a stopping rule otherwise the recursion would continue indefinitely.
  • At Step 6, n=0 and the recursion stops, the method ends and control returns to the calling method (Step 7). The calling method method has no more code to execute, so control returns to its calling method (Step 8) and finally control returns to main (Step 9) and the program ends. This process is called unwinding. The term unwind refers to the process of one method ending and returning to the method that called it.
  • Notice that the printing took place during the windingand that no real processing (i.e. no printing, etc.) took place during the unwinding, though it can as in the next example.

What would the method produce if we call it with n=4?

  1. Example 2– Next, we move the print statement in the previous example to after the recursive call as shown on the right.

Consider calling this method with n=2 as shown below. Follow the numbered steps in purple:

Notes about the execution:

  • The output of this method is:12
  • The printing took place during the unwinding.
  • The calling method retains its own value of n. For example, at Step 6, n=0 and at Step 7 we unwind to the calling method where n=1.

What would the method produce if we call it with n=4?

  1. Example 3– The example on the right looks very similar to the previous one. The only difference is:

recursivePrint( n-1 ); // Example 2

recursivePrint( --n ); // Example 3

In both cases a recursive call is made passing a value 1 less than n. The difference is that “--n” changes the value of n in the current invocation of the method. Consider calling this method with n=2 as shown below. Follow the numbered steps in purple:

Notes about the execution:

  • The output of this method is:01
  • This version (Example 3) also does the printing during the unwinding but notice that each invocation of the method changes the value of n.For example at Step 1, we enter the method with n=2 but then just before we take Step 3 (the recursive call),n is changed to 1. Thus, during the unwinding at Step 8, we print 1.

What would the method produce if we call it with n=4?

  1. Call Stack – To understand recursion it is helpful to understand the call stack. A call stack is a data structure that stores information about the active methods in a program. When a method is executing there is an active frame on the top of the stack that represents the state of the method. For example consider the hypothetical example in the figure on the right where it shows thatmain is executing and there is a local variable p with the value 7.

When a method calls another method, a frame for the method being called is pushed onto the stack and is now the active frame. For example, suppose main calls meth1, then the stack would be as shown on the right.

When a method finishes, its frame is popped from the stack and execution resumes in the calling method. For example, when meth1 finishes it is popped (removed), and main again becomes the active frame and main resumes execution with the values of its local variables found in the now active frame.

  1. Call Stack Example– In the example below main calls m1 which calls m2. Notice how the stack grows (right side of figure) as methods are called and shrinks (unwinds) as methods return (left side of figure).

  1. Call Stack Example– The figure below shows main calling recursivePrint (Example 1) with the value 2. The figure shows exactly how the stack grows and shrinks as the code executes. Take your time and study the code below carefully and verify the numbered (purple) steps below.
  1. recurPrint(2) is called, a frame is pushed onto the stack, and since , “2” is printed
  2. recurPrint(1) is called, a frame is pushed onto the stack, and since , “1” is printed
  3. recurPrint(0) is called, a frame is pushed onto the stack, and since , the method ends
  4. As the method ends, the stack is popped and execution resumes in the caller (in this case the caller has no more code to execute).
  5. Same as 4.
  6. Same as 4.

  1. A recursive definition refers to a situation where something is defined in terms of itself. Examples:
  1. The recursive definition of factorial is: where for
  2. Exponentiation can be defined recursively:
  3. The Koch snowflake

Source:

  1. Some problems are naturally recursive:
  1. Example – If someone asked you to find a particular file in a folder on your hard drive, you would look in that folder. If you didn’t see it, you would look in each subfolder. And, if still not found, you’d continue to look in sub-subfolders. A recursive algorithm (pseudo-code) for the problem is shown below. The recursive step is highlighted in yellow.

lookForFile( folder, fileName )

folderItems = folder.getItemsInFolder()

for( item : folderItems )

if( item isA File )

if( item.fileName = fileName )

Return item

else if( item isA Folder )

lookForFile( item, fileName )

  1. Example – Consider a maze as shown on the right where you enter where the red arrow is and try to find a path to the exit (green arrow). To solve this with a recursive algorithm we would model the maze as composed of a bunch of square rooms. Each room has 4 sides, some of which are walls and can’t be crossed and other are doors which can be crossed. This is the basic idea of a recursive algorithm to solve this problem:

findPath( room )

if room is destination

found = true

for( side : room.sides() )

if( !found & side isA Door )

findPath( room.side().nextRoom() )

Section 18.2 – Factorial

In mathematics, the factorialof a number is defined as the product of that number and all smaller positive integers. / The recursive definition of factorial is:
where for
Examples:
by definition




/ Example:





  1. A recursive method to computer factorial:

private static long factorial( long n ) {

return n * factorial(n-1);

}

This method has a big problem – the recursion continues forever (or until the computer runs out of memory)! A recursive method must have a stopping condition (also called a base case) which stops the recursion. For the factorial problem, we use the fact that factorial is only defined for and that by definition, . Thus, this is our base case. Thus, a correct recursive solution to the factorial problem is:

Notice also that this recursive method returns a value (an int). The recursivePrint method we looked at earlier is void, the “work” it did was simply printing. Many times we will want a recursive method to return something and this is a bit more challenging at times. We will explore this more as we move along.

  1. Let’s take a close look at how the stack functions when the recursive factorial method is used. The version of factorial we use here (not shown) uses a base case of n=0 or n=1 (which both return 1). For example, consider a call to fact(4):

  1. Consider recursivePrint which we considered earlier (Example 1, shown below). It doesn’t appear to have a stopping condition.

privatestaticvoid recursivePrint(intn) {

if( n > 0 ){

System.out.print( n + " ");

recursivePrint1(n-1);

}

}

It actually does have a stopping condition, it is just subtle. We see that every recursive call reduces n by 1. What happens when n=0? The method simply ends. Thus, the stopping condition is implicit. We could have written recursivePrint as shown below with an explicit base case and it would operate identically.

Section 18.3 – Problem: Computing Fibonacci Numbers

  1. A Fibonacci number can be recursively defined as:

, where .

Examples:

  1. Below we show a method to calculate the Fibonacci number for a given input using a recursive approach. Note that there are two base cases:
  1. Using recursion to calculate a Fibonacci number is not efficient. We are repeatedly calling Fibonaccion the same values. Consider, a trace of the recursive calculation of fibonacci(5)

Note that we have calledfib(3) twice, fib(2) 3 times, and fib(1) 5 times, etc.

  • We should never use recursion when we duplicate work by solving the same instance of a problem in separate recursive calls.

Fun Fact: For it can be proved that the number of calls to is larger than the actual Finonacci number itself! For instance, when , and the total number of recursive calls is more than 300,000,000. This is particularly ridiculous considering an iterative approach would take just 40 iterations of a loop!We say this recursive algorithm has an exponential number of recursive calls. In other words, the number of recursive calls grows exponentially as n increases.The graph on the right shows the time it took to compute Fibonacci(n) on my computer using a recursive algorithm. The time for an iterative approach is effectively 0.

Section 18.4 – Problem Solving using Recursion

  1. All recursive methods have the following characteristics:
  1. There is an if/else or switch statement that leads to different cases.
  2. One or more base cases are used to stop the recursion.
  3. Every recursive call creates a smaller version of exactly the same problem bringing it increasingly closer to a base case until it becomes that base case (stopping the recursion).

To solve a problem using recursion the key is to break the problem into sub-problems where the sub-problems are identical to the original problem, except smaller in size.

  1. Palindrome Example – We remember that a string is a palindrome if it reads the same forwards and backwards. Consider a method, isPalindrome that accepts a string and returns true if the string is a palindrome and false otherwise.
  1. An idea for a recursive algorithm to solve the problem is shown on the right. The idea is:

Base Case:

If the first and last characters are different, return false

Make the problem smaller (recursive step):

If the first and last characters are the same, remove them and then ask if the remaining string is a palindrome.

  1. However, we need another base case, one that returns true when we have exhausted all the characters. For example, in the example above, we check: “c and c”, then “o and o”, then “w and w”. Finally, there is just one character left, “o”. Of course, a single character is a palindrome. Thus, another base case is:

If the string has only one character, return true.

  1. This example had use a string whose length was odd. How would this approach work if the string had an even length? Consider, “cowwoc”. The algorithm would check: “c and c”, then “o and o”, then “w and w” which would leave an empty string. Thus, we need another stopping rule:

If the string is empty, return true.

  1. Implementation:

publicstaticboolean isPalindrome(String s) {

if(s.length() <= 1 ) // base case

returntrue;

elseif( s.charAt(0) != s.charAt(s.length()-1 )) // base case

returnfalse;

else

returnisPalindrome(s.substring(1,s.length()-1));

}

Homework
  1. Write a recursive method, printString that accepts a string and an integer. The method should print the string the number of times specified by the integer.
  2. Write a recursive method, isPalindrome that accepts a string and returns whether it is a palindrome or not.
  3. Write a recursive method to compute the factorial of an input integer.
  4. Write a recursive method to compute the Fibonacci number of an input integer.
  5. Problem 18.4 from text. Write a recursive method to compute the following series:

  1. Problem 18.5 from text. Write a recursive method to compute the following series:

  1. Problem 18.6 from text. Write a recursive method to compute the following series:

  1. Problem 18.8 from text.Write a recursive method that accepts an integer and displays it reversely on the console. For example: reverseDisplay(12345) displays 54321. Hint: (a) what is the value of 12345%10? (b) what is the value of 12345/10?
  2. Write a recursive method, reverseString that accepts an integer and returns a string with the digits of the input integer in reverse. For example: reverseString(8452) returns “2548”. Hint: similar to problem 18.8 except that you need to build the string as you recurse.
  3. (omit, hard) Write a method, reverseInt that accepts an integer and returns an integer with the digits of the input integer in reverse. For example: reverseInt(8452) returns 2548. Hint: As you extract each digit you need to multiply it by the appropriate power of 10. For example if 143 is the input, at the first iteration, you extract 3 and then need to multiply it by 10 raised to the 2 power. At the next step, you extract the 4 and multiply it by 10 raised to the 1 power. Note that you can get the exponent with this expression: (int)Math.log10(n).
  4. Problem 18.9 from text. Write a recursive method that accepts a string and displays the string reversely on the console. For example: reverseDisplay(“abcd”) displays: “dcba”.
  5. Problem 18.10 from text. Write a recursive method that accepts a string and and a character. The method should return the number of occurrences of the character in the string. For example, count(“tree house”,’e’) returns 3.
  6. Problem 18.11 from text.Write a recursive method that accepts a long and returns the sum of the digits in the long. For example, sumDigits(83197) returns 28.

Section 18.5 – Recursive Helper Methods

  1. Recursive Helper Method – Many times when recursion is the desired solution, the actual recursion takes place in a helper method. The helper method usually has at least one additional parameter that describes how far the recursion has already proceeded or how far it still has to proceed and/or a partial computation. Typically, a non-recursive (public) method (meant to be called by users) will call a recursive helper (private) methodwith the appropriate initial values for the extra parameters.
  1. Palindrome Example –
  1. As we remember, the String class is immutable and thus the substring method we used in the isPalindrome method in the previous section creates a new (smaller) string with each recursive call. As we recurse, each of these strings is pushed on to the stack. Thus, as the stack grows, more and more strings are being held in memory. If in doubt, run the previous code through the Visualizer and you will see these strings on the stack. This would be inefficient if input string is very long.
  1. Consider another approach where we use indices to indicate which characters we are comparing during each recursive call. As shown on the right we never modify the string we are checking and we also include two additional parameters, first and last that specify which two characters we are going to compare. Initially, we consider the first (index 0) and last character (index 6). Since the characters are the same, we move first and last inward to 1 and 5, respectively. Next, since these two characters (‘o’) are the same we move first and last inward again to 2 and 4, respectively. Finally, we get to a point where first and last are point to the same character, ‘o’ which by definition is a palindrome. Thus, this suggests a stopping rule that when first and last are equal, return true (we will have to modify this shortly as it doesn’t handle the case when the input string has even length).
  1. The structure of this approach is to define a public method that accepts a string, just as before. However, it calls a recursive helper method:

publicstaticboolean isPalindrome(String s) {

if(s.length() <= 1 )

returntrue;

returnisPalindrome(s,0,s.length()-1);

}

// Recursive helper method

privatestaticboolean isPalindrome(String s, intfirst, intlast) {

if(first==last) // base case – not correct, needs modification

returntrue;

elseif(s.charAt(first) != s.charAt(last)) // base case

returnfalse;

else

returnisPalindrome(s,first+1,last-1);

}

Notice that there are two base cases: one for detecting that a string is a palindrome and one for detecting that it is not.

  1. Our stopping rule above does not work when the input string has an even length. Consider the figure on the right where the input string has an even length. At the third iteration, we check the middle to characters (“ww”). We could develop a stopping rule that would stop there, but it would be a bit more complicated than it first appears. Every time we find that two characters are the same, before recursing, we would need to check if first=last-1 as shown below:

privatestaticboolean isPalindrome(String s, intfirst, intlast) {

if(first==last) // base case for odd length string

returntrue;

elseif(s.charAt(first) != s.charAt(last)) // base case

returnfalse;

else

if(first==last-1) // base case for even length string

returntrue;

else

returnisPalindrome(s,first+1,last-1);

}

  1. However, if we recurse one more time, as shown in the figure on the right we see that first>last which clearly indicates that we are done. Now, if we combine that with the stopping rule for an odd length string we arrive at a single stopping rule: first>=lastthat takes care of both even and odd length strings as shown below:

privatestaticboolean isPalindrome(String s, intfirst, intlast) {