Recursion, how it can be used and how it compares to an iterative approach

Recursion, how it can be used and compares to an iterative approach.

2.2.1 Programming Techniques

Programming Techniques — Note 2 of 6

Candidates need to understand the principle of recursion and the key features of a recursive algorithm, such as a stopping condition. Candidates need to be able to read, trace and write recursive functions, and translate between recursive and iterative solutions. Candidates need to understand the benefits and drawbacks of recursive and iterative solutions.

What you need to know

A recursive subroutine calls itself, working on a smaller version of the problem each time until it reaches a base case. Many problems, such as tree traversal and divide and conquer algorithms, are naturally recursive.

What to know

A recursive subroutine must have a BASE CASE (a stopping condition that returns a value without a recursive call) and must move towards the base case with each call.
Each call is placed on the call stack with its own parameters, local variables and return address; when the base case is reached, the calls return one by one in reverse order (unwinding).
Benefits of recursion: can be shorter and more natural for problems that are recursive in nature (e.g. tree traversal, merge sort, quick sort).
Drawbacks of recursion: uses more memory because of the stack frames; can be slower; if the base case is never reached, or the recursion is too deep, a stack overflow occurs; can be harder to trace.
Iteration uses a loop instead; it is usually more memory-efficient, but can be harder to write for naturally recursive problems.
Any recursive algorithm can be rewritten iteratively, and vice versa.

Key terms

Recursion: A subroutine that calls itself.

Exam technique

Tip:You need to read, trace and write recursive functions, and convert between recursive and iterative versions.
Mistake:Forgetting the base case, or writing a recursive call that does not move towards it.

Code examples

Factorial: recursive and iterative versions

python

def factorial_recursive(n):
    if n <= 1:                  # base case
        return 1
    return n * factorial_recursive(n - 1)   # recursive call

def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result = result * i
    return result

print(factorial_recursive(4))   # 24: 4 * 3 * 2 * 1
print(factorial_iterative(4))   # 24