- Forward


Recursion
with Examples in Java


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Recursion in Programming
Back SMYC Forward
  • 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 Under the Hood
Back SMYC Forward
  • 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
Method/Function Calls Under the Hood (cont.)
Back SMYC Forward
  • 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
Tracing the Execution of a Recursive Algorithm
Back SMYC Forward
  • 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)
Tracing the Execution of a Recursive Algorithm (cont.)
Back SMYC Forward
For simplicity, let's trace a method/function for calculating the factorial.
public static int factorial(int n) { int value; if (n == 0) value = 1; else value = factorial(n-1) * n; return value; }
Tracing the Execution of a Recursive Algorithm (cont.)
Back SMYC Forward
As a more complicated example, let's trace a method/function for calculating Fibonacci numbers.
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; }
Definition vs. Implementation of Methods/Functions
Back SMYC Forward
  • 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
Definition vs. Implementation of Methods/Functions (cont.)
Back SMYC Forward
  • 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; }
Definition vs. Implementation of Methods/Functions (cont.)
Back SMYC Forward
  • 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; }
Definition vs. Implementation (cont.)
Back SMYC Forward
  • 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; }
Multiple return Statements in Recursive Methods/Functions
Back SMYC Forward

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)); }
Thinking Recursively (i.e. Solving Problems with Recursion)
Back SMYC Forward

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
An Example - Formatting a Number in any Base
Back SMYC Forward
  • 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
An Example - Formatting a Number in any Base (cont.)
Back SMYC Forward
javaexamples/recursion/RadixFormatterV1.java
 
An Example - Searching through an Array
Back SMYC Forward
  • 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
An Example - Searching through an Array (cont.)
Back SMYC Forward

An Unsorted Array

javaexamples/recursion/searchunsorted/Searcher.java (Fragment: 0)
 
An Example - Searching through an Array (cont.)
Back SMYC Forward
  • 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)
An Example - Searching through an Array (cont.)
Back SMYC Forward

A Sorted Array Using One Base Case

javaexamples/recursion/search1/Searcher.java (Fragment: 0)
 
An Example - Searching through an Array (cont.)
Back SMYC Forward

A Sorted Array Using Two Base Cases

javaexamples/recursion/search2/Searcher.java (Fragment: 0)
 
An Example - Making Change
Back SMYC Forward
  • 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
An Example - Making Change (cont.)
Back SMYC Forward

A (Really Slow) Recursive Algorithm

javaexamples/recursion/ChangeMaker.java
 
Recursive Methods in a Class
Back SMYC Forward
  • 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
An Example - Formatting a Number in any Base
Back SMYC Forward

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
 
An Example - Making Change
Back SMYC Forward

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
 
Rewriting Recursive Methods/Functions
Back SMYC Forward
  • 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
Tail Recursion
Back SMYC Forward

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); }
Tail Recursion (cont.)
Back SMYC Forward

A tail-recursive implementation:

public static int factorial(int n, int accumulator) { if (n == 0) return accumulator; else return factorial(n-1, n*accumulator); }
Tail Recursion (cont.)
Back SMYC Forward

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; }
There's Always More to Learn
Back -