Recursion and Iteration (OCR A-Level Computer Science): Revision Notes

Recursion and Iteration

Overview

Recursion and iteration are two fundamental approaches for solving problems that involve repetitive tasks or processes. Both techniques allow programmes to repeat a set of instructions, but they do so in different ways. Understanding their principles, benefits, and drawbacks is essential for selecting the most appropriate approach for a given problem.

Recursion

Definition:

• Recursion occurs when a function calls itself to solve smaller instances of the same problem.
• Each recursive call works on a smaller problem until a stopping condition (also known as a base case) is met.

Key Features of Recursion:

1. Base Case: The condition that stops the recursion.
2. Recursive Case: The part of the function that calls itself with a smaller or simpler input.
3. Call Stack: Each recursive call is added to the call stack. The stack stores the current state of each call and unwinds once the base case is reached.

FUNCTION factorial(n)
    IF n == 0 THEN
        RETURN 1  // Base case
    ELSE
        RETURN n * factorial(n - 1)  // Recursive case
    ENDIF
END FUNCTION

Iteration

Definition:

Iteration uses loops (e.g., FOR, WHILE) to repeatedly execute a block of code until a condition is met.

Key Features of Iteration:

1. Loop Condition: A condition that determines whether the loop should continue.
2. Loop Body: The set of instructions that are executed during each iteration.
3. Termination: The loop ends when the condition is no longer true.

FUNCTION factorial(n)
    DECLARE result = 1
    FOR i = 1 TO n
        result = result * i
    ENDFOR
    RETURN result
END FUNCTION

Comparison of Recursion and Iteration

Translating Between Recursion and Iteration

Some problems can be solved using either recursion or iteration. Here's how to convert between them:

Recursive to Iterative:

• Identify the base case and recursive case.
• Replace recursive calls with a loop that replicates the function calls.

FUNCTION factorial(n)
    IF n == 0 THEN
        RETURN 1
    ELSE
        RETURN n * factorial(n - 1)
    ENDIF
END FUNCTION

FUNCTION factorial(n)
    DECLARE result = 1
    FOR i = 1 TO n
        result = result * i
    ENDFOR
    RETURN result
END FUNCTION

Iterative to Recursive:

• Replace loop logic with recursive calls.
• Include a base case to prevent infinite recursion.

FUNCTION sum(n)
    DECLARE total = 0
    FOR i = 1 TO n
        total = total + i
    ENDFOR
    RETURN total
END FUNCTION

FUNCTION sum(n)
    IF n == 0 THEN
        RETURN 0  // Base case
    ELSE
        RETURN n + sum(n - 1)  // Recursive case
    ENDIF
END FUNCTION

Benefits and Drawbacks of Recursion

Benefits of Recursion:

1. Simplifies Code for Complex Problems:

• Recursion can provide a clear, elegant solution for problems like tree traversal or divide-and-conquer algorithms (e.g., quicksort, mergesort).

2. Natural Fit for Some Problems:

• Problems that inherently involve repetitive sub-problems, such as factorials, Fibonacci sequences, and graph traversal.

Drawbacks of Recursion:

1. Higher Memory Usage:

• Each recursive call uses stack memory, which can lead to stack overflow for deep recursions.

2. Performance Overhead:

• Recursive calls involve function call overhead.

Benefits and Drawbacks of Iteration

Benefits of Iteration:

1. More Efficient:

• Uses less memory and is generally faster since it avoids the overhead of function calls.

2. Better for Large Data Sets:

• Avoids stack overflow issues.

Drawbacks of Iteration:

1. Less Intuitive for Complex Problems:

• Iterative solutions for problems like tree traversal may be harder to implement and read.

2. More Code:

• May require additional variables and lines of code for certain tasks.

Trace Tables for Recursion and Iteration

Purpose of Trace Tables:

Trace tables help track the values of variables at each step or call, making it easier to debug and understand the programme's behaviour.