Recursion Notes

Chapter Scope

• The concept of recursion

• Recursive methods

• Infinite recursion

• When to use (and not use) recursion

Recursion

• Recursion is a programming technique in which a method can call itself to fulfill its purpose.

• A recursive definition is one which uses the word or concept being defined in the definition itself.

• In some situations, a recursive definition can be an appropriate way to express a concept.

• Before applying recursion to programming, it is best to practice thinking recursively.

Infinite Recursion

• All recursive definitions must have a non-recursive part.

• If they don't, there is no way to terminate the recursive path.

• A definition without a non-recursive part causes infinite recursion.

• This problem is similar to an infinite loop -- with the definition itself causing the infinite “looping”.

• The non-recursive part is called the base case.

Recursion in Math

• Mathematical formulas are often expressed recursively.

• N!, for any positive integer N, is defined to be the product of all integers between 1 and N inclusive.

• This definition can be expressed recursively:

  • 1! = 1

  • N! = N * (N-1)!

• A factorial is defined in terms of another factorial until the base case of 1! is reached.

Recursive Programming

• A method in Java can invoke itself; if set up that way, it is called a recursive method.

• The code of a recursive method must handle both the base case and the recursive case.

• Each call sets up a new execution environment, with new parameters and new local variables.

• As always, when the method completes, control returns to the method that invoked it (which may be another instance of itself).

• Consider the problem of computing the sum of all the integers between 1 and N, inclusive.

• If N is 5, the sum is 1 + 2 + 3 + 4 + 5

• This problem can be expressed recursively as:

  • The sum of 1 to N is N plus the sum of 1 to N-1

Recursive method to compute the sum of 1 to N

public int sum(int num) {
  int result;
  if (num == 1)
  result = 1;
  else
  result = num + sum(num-1);
  return result;
}

Recursion vs. Iteration

• Just because we can use recursion to solve a problem, doesn't mean we should.

• For instance, we usually would not use recursion to solve the sum of 1 to N.

• The iterative version is easier to understand (in fact there is a formula that computes it without a loop at all).

• You must be able to determine when recursion is the correct technique to use.

• Every recursive solution has a corresponding iterative solution.

• A recursive solution may simply be less efficient.

• Furthermore, recursion has the overhead of multiple method invocations.

• However, for some problems recursive solutions are often more simple and elegant to express

Analyzing Recursive Algorithms

• To determine the order of a loop, we determined the order of the body of the loop multiplied by the number of loop executions.

• Similarly, to determine the order of a recursive method, we determine the order of the body of the method multiplied by the number of times the recursive method is called.

• In our recursive solution to compute the sum of integers from 1 to N, the method is invoked N times and the method itself is O(1)

• So the order of the overall solution is O(n)