Stack or recursion
- Algorithms course
- Intermediate
- Lesson 58/80
- 4 min
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.
Practice 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).
Starter code
def dfs_rec(graph, node, visited):
# Implement recursive DFSSample 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)Expected output
[0, 1, 3, 2]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Recursion output
def dfs(graph, node, visited):
if node in visited:
return ____def dfs(graph, node, visited):
if node in visited:
return NoneExplanation: None is right.
2 Stack or recursion: match the terms
| Term | Meaning |
|---|---|
recursion |
Self-call |
stack |
LIFO |
base |
Return |
visited |
Set |
3 What does the call stack do in recursive DFS?
- Becomes a hash table
- Becomes a queue
- Becomes a heap
- Acts as implicit stack Correct answer
Explanation: Acts as implicit stack.