Recursion Functionality – Base Case, Recursive Case, Call Stack & Stack Overflow

This post is a concept explanation of recursion – including exam questions and tags.

In a Nutshell

Recursion refers to a method in which a function calls itself directly or indirectly until a defined termination condition is reached. It is particularly suitable for problems that can be broken down into subproblems of the same structure.

Compact Technical Description

Recursive functions solve a problem by splitting it into smaller, similar subproblems. Each function calls itself with a portion of the original problem until a so-called termination condition (base case) is reached. The function call is then returned in reverse order (stack principle). Typical applications are mathematical calculations (factorial, Fibonacci numbers), tree structures, or searching recursive data models. However, memory consumption is critical because each recursive call puts a load on the stack.

Exam-Relevant Key Points

• Recursion is a self-calling principle within a function
• A termination condition prevents infinite recursion
• Each function call is stored on the call stack
• Often used for structurally repeating problems (e.g., tree structures)
• In practice, often simpler to write than iterative solutions
• Can lead to stack overflow if termination condition is missing
• More resource-intensive than iteration, as each call requires memory
• Must be documented in a traceable manner

Core Components

1. Recursive function
2. Base case (termination condition)
3. Recursive case (self-call)
4. Call stack for execution management
5. Stack overflow as an error source
6. Tail recursion as an optimization form
7. Tracing calls for debugging
8. Application to recursive data structures
9. Protection against infinite recursion
10. Unit tests to verify base and recursion logic

Practical Example

// Example: Calculating the factorial of a number
function factorial(n)
    if n == 0 then
        return 1
    else
        return n * factorial(n - 1)

Explanation: This function calls itself until n equals 0. After that, the results are returned along the call stack.

Advantages and Disadvantages

Advantages

• Shorter and often more readable implementation
• Natural for recursive structures like trees or directories
• Direct logical modeling of mathematical formulas

Disadvantages

• Higher memory consumption due to call stack
• Risk of stack overflow with deep recursion
• More difficult to debug than iterative approaches

Typical Exam Questions (with Short Answer)

1. Recursion in programming? Function that calls itself to solve a problem through subproblems.
2. Condition recursive function must contain? Termination condition to avoid infinite calls.
3. Typical application example for recursion? Traversal of tree structures, e.g., in file systems or XML data.
4. Stack overflow with recursion? Error when too many function calls exceed stack memory.
5. Recursive vs. iterative problem solving? Recursion uses self-calls, iteration uses loop structures.
6. Danger of incorrect termination condition? Function calls itself endlessly and leads to a stack overflow.
7. Optimization form for recursion? Tail recursion, which can be optimized to iterations by the compiler.
8. Document recursion? Through flowcharts, pseudocode, and call stack analyses.

Most Important Sources

1. https://stackoverflow.com/questions/2693676
2. https://javascript.info/recursion
3. https://www.geeksforgeeks.org/recursion-in-programming