Recursion

Recursion
with Examples in Java

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Recursion in Programming

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

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.)

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

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.)

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.)

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

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.)

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.)

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.)

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

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)

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

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.)

javaexamples/recursion/RadixFormatterV1.java

An Example - Searching through an Array

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.)

An Unsorted Array

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

An Example - Searching through an Array (cont.)

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.)

A Sorted Array Using One Base Case

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

An Example - Searching through an Array (cont.)

A Sorted Array Using Two Base Cases

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

An Example - Making Change

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.)

A (Really Slow) Recursive Algorithm

javaexamples/recursion/ChangeMaker.java

Recursive Methods in a Class

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

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

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

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

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.)

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.)

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