Recursion in Java

Flashcards on Recursion in Java

Recursive Definition

A definition that defines something in terms of itself, requiring a base case and an inductive case to avoid infinite regress.

Base Case (Anchor)

Part of a recursive definition that does not reference its own type.

Inductive Case

Part of a recursive definition that contains a reference to its own type.

Recursion

A technique where a method makes one or more calls to itself during execution.

Recursive Program/Algorithm

A program or algorithm that calls itself again during execution.

Three Basic Rules for Developing Recursive Algorithms

Know how to take one step, break down problems into one step plus a smaller problem, and know how and when to stop.

Purposes of Recursive Definition

Generating new elements and testing whether an element belongs to a set.

Contents of an Activation Record (AR)

Parameters and local variables, a dynamic link, return address, and return value.

Return Address

The address of the caller’s instruction immediately following the call.

Run-Time Stack & Activation Records

Each new activation record is placed on the top of the run-time stack; the first AR in is the last one out.

Linear Recursion

Only 1 recursive call inside the recursive function.

Binary Recursion

Exactly 2 recursive calls inside the recursive function.

Multiple Recursion

3 or more recursive calls inside the recursive function.

Tail Recursion

Only one recursive call at the very end of a method implementation.

Non-Tail Recursion

The recursive call is not at the very end of a method implementation.

Indirect Recursion

When f() calls g(), and g() calls f().

Nested Recursion

A function is defined in terms of itself and also used as one of the parameters.

Excessive Recursion (in Fibonacci Sequence)

An implementation of the Fibonacci sequence that looks natural but is extremely inefficient due to repeated calculations.

Rules of the Tower of Hanoi

Only one disk may be moved at a time, each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod. no disk may be placed on top of a smaller disk.

Recursion vs. Iteration

When possible, iteration is usually better due to no overhead of the run-time stack. Some recursive algorithms are very difficult to do any other way.