Stack or recursion

DFS uses a stack or recursion.

Stack or recursion

DFS is implemented explicitly with a stack or implicitly with recursion. Recursion uses the call stack.

Both give LIFO behavior; the choice is stylistic and the result is the same.

Recursion reads shorter; a stack avoids overflow on deep graphs and is preferred in practice.

Recursion base

In recursive DFS the base case is the visited set: if a vertex was seen, the call returns immediately.

This check is essential to prevent infinite loops; each vertex is processed only once.

The base case stops recursion and reduces stack overflow risk; this is why it matters.

Exercise Recursive DFS

Write recursive dfs_rec(graph, node, visited). Append visit order to the visited list. Print [0, 1, 3, 2] with v=[]; dfs_rec({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0, v); print(v).

Show example solution

def dfs_rec(graph, node, visited):
    # Implement recursive DFS
    if node not in visited:
        visited.append(node)
        for nb in graph[node]:
            dfs_rec(graph, nb, visited)
v = []
dfs_rec({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0, v)
print(v)

Test yourself

Recursion output

def dfs(graph, node, visited):
    if node in visited:
        return ____

Show answer

def dfs(graph, node, visited):
    if node in visited:
        return None

Stack or recursion: match the terms

recursion

Self-call
stack

LIFO
base

Return
visited

Set
What does the call stack do in recursive DFS?
- Becomes a hash table
- Becomes a queue
- Becomes a heap
- Acts as implicit stack
Show answer

Acts as implicit stack — Acts as implicit stack.

Next lesson: Backtracking

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies