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)