Stack Depth

The stack depth refers to the maximum number of pending function calls as a measure of recursive depth. Tracking stack depth allows detecting stack overflows from excessive recursion.

Some ways to track stack depth:

• Explicitly pass and increment depth parameter
• Exception handler to print stack trace
• Runtime introspection of stack size

Java - Explicit depth parameter:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void recursiveFunc(int depth) {
  if (depth > MAX_DEPTH) {
    throw new StackOverflowError();
  }
  
  // Recursive call
  recursiveFunc(depth+1);
}

// Initial call
recursiveFunc(0);

C++ - Stack unwinding with exceptions:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void recursiveFunc() {
  
  try {
    recursiveFunc(); 
  } catch(exception& e) {
    int depth = e.what(); // Get depth from exception
  }

}

// Custom exception class to carry depth

Python - Introspect stack size:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import inspect

def recursive_func():

  stack_depth = len(inspect.stack())
  
  if stack_depth > MAX_DEPTH:
    raise StackOverflowError
  
  recursive_func()
  
recursive_func()

Tracking stack depth allows detecting and preventing stack overflows from unbounded recursion.

Stack depth refers to the level of nested function calls in a program. When a function is called, its local variables, parameters, and return addresses are stored on the stack. Each new function call adds another layer, increasing the stack depth. Understanding stack depth is crucial for analyzing the resource usage of recursive algorithms and avoiding stack overflow errors.

Let’s consider finding the factorial of a number as an example to demonstrate stack depth in recursive functions.

Java

Here’s the Java version:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public class StackDepth {
    static int factorial(int n) {
        if (n == 0) return 1;
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        int result = factorial(5);
        System.out.println("Factorial of 5 is: " + result);
    }
}

In this Java code, each call to factorial adds a new layer to the stack until n becomes 0.

C++

Here’s the C++ version:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

int main() {
    int result = factorial(5);
    cout << "Factorial of 5 is: " << result << endl;
    return 0;
}

In C++, each function call also increases the stack depth.

Python

Here’s the Python version:

1
2
3
4
5
6
7

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

result = factorial(5)
print("Factorial of 5 is:", result)

In Python, stack depth works similarly. Each recursive call to factorial increases the stack depth.

In all three versions, the stack depth would reach up to n+1 for an input n as the recursive calls pile up on the stack. Once the base case is hit, the stack starts to unwind, computing the factorial and returning it.