Recursion in Java

Recursive Definition

• Defines something in terms of itself.
• Requires a base case (anchor) and an inductive case.
• Base case: does not reference its own type.
• Inductive case: references its own type.
• Examples:
  • Factorial: n! = \begin{cases} 1 & \text{if } n = 0 \ n*(n-1)! & \text{if } n>0 \end{cases}
  • Fibonacci sequence: fibo(n) = \begin{cases} n & \text{if } n<2 \ fibo(n-1) + fibo(n-2) & \text{otherwise} \end{cases}

Recursive Program/Algorithm

• A method makes one or more calls to itself.
• Achieves repetition through recursion instead of loops.
• Requires:
  • Knowing how to take one step.
  • Breaking the problem into one step plus a smaller problem.
  • Knowing how and when to stop.

Recursion Application

• Used in defining functions or sequences.
• Purpose:
  • Generating new elements.
  • Testing set membership by reducing to simpler problems.

Method Calls and Recursion Implementation

• Each method call allocates an activation record (AR) containing:
  • Parameters and local variables.
  • Dynamic link to the caller's AR.
  • Return address.
  • Return value (if not void).
• ARs are placed on a run-time stack; the first AR in is the last out.
• Recursion is an instantiation of a method calling another instantiation of itself, differentiated by activation records.

Anatomy of a Recursive Call

• Demonstrates how recursive calls are stacked and resolved to compute a value (e.g., factorial).

Classification of Recursion

• Based on the number of recursive calls within a single activation:
  • Linear recursion: 1 recursive call.
  • Binary recursion: 2 recursive calls.
  • Multiple recursion: 3 or more recursive calls.

Tail Recursion

• Only one recursive call, and it is the very last operation in the method.

Non-Tail Recursion

• The recursive call is not the last operation; there are operations after the recursive call.

Indirect Recursion

• f() calls g(), and g() calls f().
• Can involve a chain of calls: f() -> f1() -> f2() -> … -> fn() -> f().

Nested Recursion

• A function is defined in terms of itself and also used as one of the parameters.
• Example: Ackermann's function.

Excessive Recursion

• Inefficient implementations, like the naive Fibonacci sequence calculation due to repeated calculations.

Recursion vs. Iteration

• Iteration is often better when possible due to the overhead of the run-time stack in recursion.
• Some algorithms are more naturally expressed recursively.