• An Informal Definition:
  • A method calls itself (either directly or indirectly)
• An Example:

  •     public static int factorial(int n)
        {
          int value;
    
          if   (n == 0) value = 1;
          else          value = factorial(n-1) * n;
    
          return value;
        }
    	

• Method/Function Calls:
  • When a method is called an activation record (or invocation record or stack frame) is created
  • Method calls/returns happen in a last-in-first-out manner
• Activation Records Contain:
  • Local variables and their values
  • The location (in the caller) of the function call
  • Execution status (e.g., processor registers) of the current module
  • Other things

• Non-Recursive Methods/Functions:
  • Until now we didn't consider any examples in which two methods/functions had parameters or local variables with the same name
  • Now we know that an invocation record exists for each and the one on the top of the stack is used
• Recursive Methods/Functions:
  • We can and should think about instances of method calls

• Use "Cards" for Activation Records:
  • Each card contains the local variables and their values
  • Each card contains the location (in the caller) of the method call
• Tracing Execution:
  • Add a "card" to the top of a stack when a method is called and remove a "card" when the method returns (which is a last-in-first-out process)

public static int factorial(int n)
{
    int value;

    if   (n == 0) value = 1;
    else          value = factorial(n-1) * n;

    return value;
}
  

public static int fibonacci(int n)
{
    int value;

    if      (n == 0) value = 0;
    else if (n == 1) value = 1;
    else             value = fibonacci(n-1) + fibonacci(n-2);

    return value;
}
  

• Recall:
  • It is often convenient to define a method/function using recursion
• A Common "Mistake":
  • This doesn't mean that the method/function should be implemented using recursion

• A Recursive Definition:
  • \(0! = 1\)
  • \(n! = (n-1)! \cdot n\)
• A Recursive Implementation:

  • public static int factorial(int n)
    {
        int value;
    
        if   (n == 0) value = 1;
        else          value = factorial(n-1) * n;
    
        return value;
    }
    	

• A Recursive Definition:
  • \(0! = 1\)
  • \(n! = (n-1)! \cdot n\)
• An Iterative Implementation:

  • public static int factorial(int n)
    {
        int value;
        
        value = 1;
        for (int i=2; i<=n; i++)
        {    
            value *= i;
        }
        
        return value;
    }
    	

• A Recursive Definition:
  • \(0! = 1\)
  • \(n! = (n-1)! \cdot n\)
• A "One-Pass" Implementation:

  • public static int factorial(int n)
    {
        int    value;
        int[]  f={1,1,2,6,24,120,720,5040,40320,
                  362880,3628800,39916800,479001600};
    
        if (n > 12) value = -1; // Or throw an exception
        else        value = f[n];
    
        return value;
    }
    	

Some people find it easier to understand recursive methods/functions when they have multiple return statements.

public static int factorial(int n)
{
    if   (n == 0) return 1;
    else          return factorial(n-1) * n;
}
  

public static int fibonacci(int n)
{
    if      (n == 0) return 0;
    else if (n == 1) return 1;
    else             return (fibonacci(n-1) + fibonacci(n-2));
}
  

A Summary

• The Process:
  • Identify the Base Case(s) (i.e., the case(s) that can be solved without recursion)
  • Refine the Other Cases (i.e., develop a way to move the other cases towards a/the base case; make progress)
• Refinement and Recursive Functions:
  • Move the parameters of the function that correspond to other cases towards the parameters that correspond to base cases
  • Use the value returned by the function call to move the answer closer to the correct answer

• The Base Case:
  • The number can be represented in one digit
• Refinement:
  • Move the parameters closer: eliminate a digit by dividing by the base
  • Move the answer closer: append the digit

javaexamples/recursion/RadixFormatterV1.java

/**
 * A class that uses recursion to format a number in any base/radix
 * (in the interval [2, 36])
 *
 * @author  Prof. David Bernstein, James Madison Unversity
 * @verions 1.0
 */
public class RadixFormatter
{
    private final int    MAX_BASE    = 36;
    private final char[] DIGIT_TABLE = {'0','1','2','3','4','5','6','7','8',
                                        '9','A','B','C','D','E','F','G','H',
                                        'I','J','K','L','M','N','O','P','Q',
                                        'R','S','T','U','V','W','X','Y','Z'
                                       };



    /**
     * The "exposed" interface.  This function does
     * initialization and error-checking.
     *
     * @param n    The number to print
     * @param base The base to use
     * @return     The formatted String
     */
    public static String formatInBase(int n, int base)
    {
        String         returnString;
        
        returnString = "";
        if ((base <= 1) || (base > MAX_BASE)) 
        {
            returnString = "Invalid base: "+base;
        } 
        else 
        {
            if (n < 0) 
            {
                returnString = "-";
                n = -n;
            }

            returnString += formatRecursively(n, base);
        }

        return returnString;
    }




    /**
     * The recursive function
     *
     * @param n    The number to print
     * @param base The base to use
     */
    private static String formatRecursively(int n, int base)
    {
        // Base Case
        if (n < base) return DIGIT_TABLE[n % base];

        // Refinement
        return formatRecursively(n/base, base)  + DIGIT_TABLE[n % base];
    }
    
}
        

• The Base Case:
  • When the interval contains one element
• Refinement:
  • Move the parameters closer: Divide the interval in half
  • Move the answer closer: Update the index

javaexamples/recursion/searchunsorted/Searcher.java (Fragment: 0)

    /**
     * Search through (part of) an array of Comparable objects
     * for a particular target.
     *
     * @param first  The first index to consider (inclusive)
     * @param last   The last index to consider (inclusive)
     * @param target The Comparable object to search for
     * @param data   The array of Comparable objects
     * @return       The index of the target (or -1 if it isn't found)
     */ 
    public static int search(int first, int last, 
                             Comparable target, Comparable[] data)
    {
        int      left, middle, result, right;
        

        result = -1;
        
        if (first == last) // The base case
        {
            if (target.compareTo(data[first]) == 0)
            {
                result = first;                
            }
        }
        else              // Refinement (i.e., shrink the search space)
        {
            middle = (first + last) / 2;
            // Note: This can be done more efficiently.
            //       You should think about how!
            left   = search(first, middle, target, data);
            right  = search(middle + 1, last, target, data);                
            result = Math.max(left, right);
        }
        return result;
    }
        

• An Observation about Sorted Arrays:
  • As when looking for a word in a dictionary, we can quickly determine if the target can possibly be in the portion of the array being considered using the value at the two ends of the range
• Implications:
  • We don't always have to recurse
  • This can make the recursive algorithm much more efficient than the iterative algorithm (which is a topic for CS240)

javaexamples/recursion/search1/Searcher.java (Fragment: 0)

    /**
     * Search through (part of) a sorted array of Comparable objects
     * for a particular target.
     *
     * @param first  The first index to consider (inclusive)
     * @param last   The last index to consider (inclusive)
     * @param target The Comparable object to search for
     * @param data   The sorted array of Comparable objects
     * @return       The index of the target (or -1 if it isn't found)
     */ 
    public static int search(int first, int last, 
                             Comparable target, Comparable[] data)
    {
        int      left, middle, result, right;
        

        result = -1;
        
        if (first == last) // The base case
        {
            if (target.compareTo(data[first]) == 0)
            {
                result = first;                
            }
        }
        else              // Refinement (i.e., shrink the search space)
        {
            if ((target.compareTo(data[first]) >= 0) &&
                (target.compareTo(data[last])  <= 0))
            {
                middle = (first + last) / 2;
                // Note: This can be done more efficiently.
                //       You should think about how!
                left   = search(first, middle, target, data);
                right  = search(middle + 1, last, target, data);                
                result = Math.max(left, right);
            }
        }
        return result;
    }
        

javaexamples/recursion/search2/Searcher.java (Fragment: 0)

    /**
     * Search through (part of) a sorted array of Comparable objects
     * for a particular target.
     *
     * @param first  The first index to consider (inclusive)
     * @param last   The last index to consider (inclusive)
     * @param target The Comparable object to search for
     * @param data   The sorted array of Comparable objects
     * @return       The index of the target (or -1 if it isn't found)
     */ 
    public static int search(int first, int last, 
                             Comparable target, Comparable[] data)
    {
        int      left, middle, result, right;
        

        result = -1;
        
        // One base case
        if (first == last) 
        {
            if (target.compareTo(data[first]) == 0)
            {
                result = first;                
            }
        }
        // Another base case
        else if ((target.compareTo(data[first]) < 0) ||
                 (target.compareTo(data[last])  > 0))
        {
            result = -1;
        }
        // Refinement (i.e., shrink the search space)
        else              
        {
            middle = (first + last) / 2;
            // Note: This can be done more efficiently.
            //       You should think about how!
            left   = search(first, middle, target, data);
            right  = search(middle + 1, last, target, data);                
            result = Math.max(left, right);
        }
        return result;
    }
        

• The Base Case:
  • Only one coin is needed
• Refinement:
  • Move the parameters closer: Iteratively split the amount into two
  • Move the answer closer: Calculate the number of coins required and determine if it is smaller

javaexamples/recursion/ChangeMaker.java

/**
 * A class that uses recursion to make change
 *
 * @author  Prof. David Bernstein, James Madison Unversity
 * @verions 1.0
 */
public class ChangeMaker
{

    /**
     * Determine the minimum number of coins needed to make change
     *
     * @param coins  The array of coin values
     * @param amount The amount of change
     *
     * @returns      The number of coins
     */
    public int change(int[] coins, int amount)
    {
        int i, j, min, number;
        
        min = amount;
        
        // If we can make change with one coin then we are done
        //
        for (i=0; i < coins.length; i++) {
            
            if (coins[i] == amount) return 1; // The base case
        }
        
        // Refine the solution
        //
        for (j=1; j <= (amount/2); j++) {
            
            number = change(coins, j) + change(coins, amount-j);
            if (number < min) min = number;
        }
        
        return min;
    }

}
    




        

• An Observation:
  • Most discussions of recursion do not consider whether OOP facilitates or complicates the development of recursive algorithms
• Why Would It Matter?
  • Attributes can be used to shorten the parameter list (which also makes it easier to understand the actual domain of the method) and to keep track of the results of the recursion
  • The recursive method can be private; the public method need not require the caller to know that it is recursive

The public method does not require the caller to know anything about the recursion.

The base attribute is used to keep track of the base (rather than passing it as a parameter).

javaexamples/recursion/RadixFormatter.java

/**
 * A class that uses recursion to format a number in any base/radix
 * (in the interval [2, 36])
 *
 * This version uses an attribute to keep track of the base.
 *
 * @author  Prof. David Bernstein, James Madison Unversity
 * @verions 2.0
 */
public class RadixFormatter
{
    private final int      MAX_BASE    = 36;
    private final String[] DIGIT_TABLE = {"0","1","2","3","4","5","6","7","8",
                                          "9","A","B","C","D","E","F","G","H",
                                          "I","J","K","L","M","N","O","P","Q",
                                          "R","S","T","U","V","W","X","Y","Z"
                                         };
    private int base;
    

    /**
     * Constructor
     */
    public RadixFormatter(int base)
    {
        this.base = base;
    }

    /**
     * The "exposed" interface.  This function does
     * initialization and error-checking.
     *
     * @param n    The number to print
     * @return     The formatted String
     */
    public String formatInBase(int n)
    {
        String formatted = "";
        
        if ((base <= 1) || (base > MAX_BASE)) 
        {
            formatted = "Invalid base: "+base;
        } 
        else 
        {
            if (n < 0) 
            {
                formatted = "-";
                n = -n;
            }
            
            formatted += formatRecursively(n);
        }

        return formatted;
    }




    /**
     * The recursive function
     *
     * @param n    The number to print
     */
    private String formatRecursively(int n)
    {
        // Base Case
        if (n < base) return DIGIT_TABLE[n % base];
        
        // Refinement
        return formatRecursively(n/base) + DIGIT_TABLE[n % base];
    }
    
}
        

An attribute can be used so that the coins array does not have to be a parameter of the recursive method.

javaexamples/recursion/CashRegister.java

/**
 * A class that uses recursion to make change
 *
 * @author  Prof. David Bernstein, James Madison Unversity
 * @verions 1.0
 */
public class CashRegister
{
    private int[]       coins;
    
    /**
     * Explicit Value Constructor.
     *
     * @param coins   The face value of the coins to use
     */
    public CashRegister(int[] coins)
    {
        this.coins = new int[coins.length];        
        System.arraycopy(coins, 0, this.coins, 0, coins.length);
    }
    

    /**
     * Determine the minimum number of coins needed to make change
     *
     * @param amount The amount of change
     * @returns      The number of coins
     */
    public int change(int amount)
    {
        int i, j, min, number;
        
        min = amount;
        
        // If we can make change with one coin then we are done
        //
        for (i=0; i < coins.length; i++) {
            
            if (coins[i] == amount) return 1; // The base case
        }
        
        // Refine the solution
        //
        for (j=1; j <= (amount/2); j++) {
            
            number = change(j) + change(amount-j);
            if (number < min) min = number;
        }
        
        return min;
    }

}
    




        

• An Observation:
  • Any recursive method/function can be re-written as a non-recursive method/function by using a stack to keep track of "state variables"
• A Special Case - Tail Recursion:
  • A method/function in which the very last action is to call itself
  • Such methods/functions can be written non-recursively by reassigning the formal parameters to the actual parameters (specified in the call) and repeating the function

Is this implementation tail-recursive? In other words, what is the last action performed?

    public static int factorial(int n)
    {
      if   (n == 0) return 1;
      else          return n*factorial(n-1);
    }
  

A tail-recursive implementation:

    public static int factorial(int n, int accumulator)
    {
      if   (n == 0) return accumulator;
      else          return factorial(n-1, n*accumulator);
    }
  

Converting a tail-recursive implementation to an iterative implementation:

    public static int factorial(int n, int accumulator)
    {
      while (n != 0)
      {
          accumulator *= n;
          n -= 1;
      }
      return accumulator;
    }