Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Recursion Recap

Recursion is a repetitive process in which an algorithm calls itself. Each call solves an identical but smaller problem, and a test for the base case stops the calls. A recurrence relation links the th term of a sequence to earlier terms, and it needs an initial condition to start.

Steps to Analyse a Recursive Algorithm

Steps:

  • decide on a parameter for the input size
  • identify the basic operation of the algorithm
  • find the worst case for an input of size
  • set up a recurrence for the number of basic operations, with an initial condition
  • solve it by backward substitution or another method

For the factorial, with counts multiplications, which gives , so .

Example: Reversing an Array

The function swaps the outer pair and , then reverses the inner part recursively. It stops when .

def ReverseArray(A, i, j):
    if i < j:
        temp = A[i]          # temp is needed to swap
        A[i] = A[j]
        A[j] = temp
        ReverseArray(A, i + 1, j - 1)
 
A = [5, 3, 2, 6]
ReverseArray(A, 0, len(A) - 1)
print(A)                     # [6, 2, 3, 5]

Time Analysis

Let be the number of swaps to reverse elements. Reversing elements needs one swap plus reversing a subarray of elements, and :

Backward substitution:

So the algorithm is .

Recursion Can Be Inefficient

Short and clear recursive code can hide a big cost. The Fibonacci numbers are with , .

Comparison:

  • the iterative version computes in steps, so
  • the naive recursive version calls itself twice per call and recomputes the same values again and again, so the total number of calls grows exponentially
def fib(n):                  # exponential number of calls
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)