CSCI 201: Intro to Programming (Java)

Lab 4: Working with recursion

This lab is devoted to recursion.

PART I: Recursive function calls

We start with the classical example of a recursive function for computing n! based on the formula n! = n * (n-1)!:

int n = factorial(n);
. . .
. . .
public static int factorial(n)
{
  if (n==1) return(1);           // termination condition
  return (n* factorial(n-1));    // recursive call
}

Lab Task I

1. Turn the given code into Netbeans project named Factorial, compile it and run. Make sure you understand how it works. Ask the instructor for clarification, if needed.
2. Write a program containing a recursive function for outputting a string character-by-character. You can use the following algorithm:

   String s = "abcdefgh"; writeString(s, 0); // function call . . . . . . // prints string s starting with character at index i public static void writeString(String s, int i) { if (i == s.length()) return(); // termination condition Output(s.charAt(i)); // print the i-th char of s writeString(s, i+1); // recursive call }

3. Turn this code into Netbeans project.
4. Modify your code so that the string outputs backwards.

PART II. Multiple recursion calls

Consider Fibonacci sequence of integer numbers. The first two numbers in that sequence are 1 and 1. Every other number is the sum of the two previous ones. In other terms, Fibonacci sequence can be defined by a recursion:

f₀ = f₁ = 1
f_n = f_n-1 + f_n-2   for n ≥ 2

A high-level recursive routine for generating such sequence is straightforward.

public static int fib(int n)
{
  if (n < 2) return(1);     // termination condition
  return fib(n-1) + fib(n-2);  // recursive call
}

Lab Task II

1. Turn this code into a working program.
2. Compile that code and run it for small values: 1, 2, 3, 4, 5.
3. Run the code for large values: 40, 41, 42. Why it gets so slow?

PART III. Memorized recursion.

It turns out that the number of recursive calls in the previous implementation grows exponentially. This is what generally happens if one have multiple (more than 1) recursive calls in a recursive function.

To improve the situation, we store a computed for the first time value of fib(m) in a local array. Then, first check if the value fin(m) was computed before, and in this case take it from the table. This idea can be implemented as it is shown in the following Java code:

public class Fibonacci
{
  private static int[] fibNumbers;

  public static void main(String[] args)
  {
    int n = Integer.parseInt(args[0]);  // get n from the command line
    fibNumbers = new int[n];        // create and initialize array for
    for (int i=0; i<n; i++)         // computed Fibonacci numbers
      fibNumbers[i] = 0;
    System.out.print("Applying the memorized recursion: fib(" + n + ")=");
    int f = fib(n);                 // apply the accelerated method 
    System.out.println(f);
  }

  // memorized recursive implementation of the same sequence
  public static int fib(int n)
  {
    if (n <= 1) return(1);   // termination condition
    int a, b;

    if (fibNumbers[n-1] != 0) // if the (n-1)-th Fib. number
      a = fibNumbers[n-1];   // is already computed, take it from the table
    else
    {                        // otherwise apply the recursion to compute it
      a = fib(n-1);         // and store in variable a
      fibNumbers[n-1] = a;
    }

    if (fibNumbers[n-2] != 0) // same approach for the (n-2)-th
      b = fibNumbers[n-2];                   // number
    else
    {
      b = fib(n-2);                         // store it in b
      fibNumbers[n-2] = b;
    }

    return(a+b);
  }
}

Lab Task III

1. Save the above Java code in file Fibonacci.java on your server account.
2. Compile it as

   javac Fibonacci.java

3. Run it for values below 45 as

   java Fibonacci 40

   Here 40 is the sequence number. The program now runs very fast now.