AI-Generated Content

This exam was created by a large language model. Please use it with caution, as inaccuracies may be present. Always verify critical information.

What is a Call Stack? Define its fundamental purpose in program execution.

Describe the mechanism by which recursive function calls are added to and removed from the call stack, illustrating the flow of execution.

Explain the conditions under which a 'stack overflow' error arises, specifically in the context of a deeply nested recursive function call, such as traversing an extremely deep folder structure.

Recursion vs. Iteration for Folder Traversal

When dealing with tasks like traversing a file system, recursion can seem intuitive, but it carries the risk of a 'stack overflow' for very deep structures. Below, we'll examine a problematic recursive approach and then refactor it into a more robust iterative solution.

Problematic Recursive Folder Traversal Example

Consider the following Python function designed to traverse a folder structure:


import os

def traverse_folder_recursive(path): """ Recursively traverses a folder structure, printing files and subdirectories. This function is prone to stack overflow for very deep directory trees. """ if not os.path.exists(path): print(f"Path does not exist: {path}") return if not os.path.isdir(path): print(f"File: {path}") return

print(f"Directory: {path}") try: for item in os.listdir(path): item_path = os.path.join(path, item) traverse_folder_recursive(item_path) # Recursive call except PermissionError: print(f"Permission denied for: {path}")

Refactored Iterative Folder Traversal Example

To avoid the stack overflow issue, we can refactor the recursive approach into an iterative one using an explicit stack:


import os
from collections import deque

def traverse_folder_iterative(path): """ Iteratively traverses a folder structure using an explicit stack (deque). This approach avoids stack overflow for deep directory trees. """ if not os.path.exists(path): print(f"Path does not exist: {path}") return

Use a deque as an explicit stack for managing directories to visit

stack = deque([path])

while stack: current_path = stack.pop() # LIFO behavior for DFS

if not os.path.isdir(current_path): print(f"File: {current_path}") continue

print(f"Directory: {current_path}") try: items = [] for item in os.listdir(current_path): items.append(os.path.join(current_path, item))

Push items onto the stack. We reverse the list of items from os.listdir

        # to ensure a consistent traversal order (e.g., if we want to process
        # children in alphabetical order, or simply to ensure all children are pushed).
        # The exact order of pushing/popping influences the traversal order (DFS).
        for item_to_push in reversed(items):
             stack.append(item_to_push)

except PermissionError: print(f"Permission denied for: {current_path}")

Referring to the traverse_folder_recursive function, explain why this recursive approach is problematic and can lead to a 'stack overflow' error when traversing an extremely deep directory tree.

Referring to the traverse_folder_iterative function, explain how this iterative approach avoids the 'stack overflow' issue encountered by its recursive counterpart.

Beyond avoiding stack overflow, what are the other potential benefits of using an iterative approach (like traverse_folder_iterative) over a recursive one for tasks like deep folder traversal?