B2.4.4 Fundamental Concept of Recursion and Its Applications in Programming (HL only) Notes

The Fundamental Concept of Recursion

Key Components of Recursion

1. Base Case: The condition that terminates the recursion. Without it, the function would call itself indefinitely, leading to a stack overflow.
2. Recursive Case: The part of the function where it calls itself with a modified version of the original problem.

Advantages and Limitations of Recursion

Advantages

1. Simplicity: Recursive solutions are often more elegant and easier to understand than their iterative counterparts.
2. Problem Decomposition: Recursion naturally breaks down complex problems into smaller, manageable parts.

Limitations

1. Memory Usage: Each recursive call adds a new frame to the call stack, which can lead to stack overflow for deep recursions.
2. Performance: Recursive algorithms can be less efficient than iterative ones due to the overhead of multiple function calls.

Applications of Recursion

Solving Problems with Smaller Subproblems

1. Recursion is ideal for problems that can be divided into smaller, similar subproblems.
2. Examples include:
   1. Factorial Calculation: As shown earlier, the factorial of a number is defined in terms of the factorial of a smaller number.
   2. Fibonacci Sequence: Each term is the sum of the two preceding terms, making it a natural fit for recursion.

Recursive Algorithms

Quicksort

Quicksort is a divide-and-conquer algorithm that uses recursion to sort an array.

1. Choose a Pivot: Select an element as the pivot.
2. Partition: Rearrange the array so that elements less than the pivot are on the left, and elements greater than the pivot are on the right.
3. Recursively Sort: Apply the same process to the left and right subarrays.

Traversing Data Structures

Binary Trees

Recursion is ideal for traversing binary trees, as each subtree is itself a binary tree.

Fractal Image Creation

1. Definition:
   1. Fractals are geometric shapes that display self-similarity — meaning the same pattern repeats at different scales.
2. How They Are Created:
   1. Recursion is used to generate fractals.
   2. A simple rule or process is repeated multiple times.
   3. Each repetition produces a smaller, scaled version of the original pattern.
3. Examples of Fractals:
   1. Koch Snowflake – built by recursively adding triangles.
   2. Sierpinski Triangle – created by recursively removing smaller triangles.
   3. Mandelbrot Set – a famous fractal generated by iterating a mathematical function.
4. Key Idea:
   1. Complexity emerges from simplicity: by applying a simple rule repeatedly, fractals can create highly intricate and infinite patterns

Limitations of Recursion

Complexity and Memory Usage

1. Stack Overflow: Recursive algorithms can exhaust the call stack if the recursion depth is too great.
2. Memory Overhead: Each recursive call consumes additional memory for the call stack.

Performance

1. Recursive algorithms can be slower than iterative ones due to the overhead of function calls.
2. Some problems, like calculating the Fibonacci sequence, have exponential time complexity when implemented recursively without optimization.

Situations Best Suited for Recursion

1. Problems with Natural Recursive Structure: Such as tree traversal and fractal generation.
2. Divide-and-Conquer Algorithms: Like quicksort and merge sort.
3. Backtracking Problems: Such as solving mazes or the N-Queens problem.