Algorithm
Understanding Recursion, Stacks, Queues, and Depth-First Search
When learning programming, recursion and data structures like stacks and queues are essential topics. These concepts are widely used in problem-solving, including algorithms like Depth-First Search (DFS). In this article, we will explore:
- Recursion and how it works
- Stack data structure and its operations
- Queue data structure and its differences from stacks
- Depth-First Search (DFS) and how it utilizes recursion
1. Recursion: The Foundation of Many Algorithms
What is Recursion?
Recursion is a programming technique where a function calls itself to solve a problem. A recursive function usually has two parts:
- Base case – Stops the recursion when a condition is met.
- Recursive case – Calls itself with a smaller problem.
Example: Factorial Calculation
Factorial (n!) is defined as:
n! = n × (n-1) × (n-2) × ... × 1A recursive function for factorial in C++:
int fact(int n) {
if (n == 0) return 1;
return n * fact(n - 1);
}
2. Stack: A LIFO Data Structure
What is a Stack?
A stack is a Last In, First Out (LIFO) data structure, meaning the last item added is the first to be removed.
Stack Operations:
push(x): Adds an item on top.pop(): Removes the top item.top(): Views the top item.
Example of Stack Usage in C++
#include <stack>
#include <iostream>
using namespace std;
int main() {
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
cout << s.top() << endl; // 3
s.pop();
cout << s.top() << endl; // 2
return 0;
}
3. Queue: A FIFO Data Structure
What is a Queue?
A queue follows First In, First Out (FIFO), meaning the first element added is the first to be removed.
Queue Operations:
push(x): Adds an element to the back.pop(): Removes the front element.front(): Views the front element.
Example of Queue Usage in C++
#include <queue>
#include <iostream>
using namespace std;
int main() {
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
cout << q.front() << endl; // 1
q.pop();
cout << q.front() << endl; // 2
return 0;
}
Stack vs Queue Comparison
| Feature | Stack (LIFO) | Queue (FIFO) |
|---|---|---|
| Insertion | push(x) adds to top |
push(x) adds to back |
| Removal | pop() removes top |
pop() removes front |
| Order | Last in, first out | First in, first out |
4. Depth-First Search (DFS) and Recursion
What is DFS?
DFS is an algorithm for traversing trees or graphs. It starts at a node, explores as far as possible along each branch before backtracking.
Example of DFS in a Tree
1
/ \
2 7
/ \ \
3 6 11
/ \ \
4 5 8
/ \
9 10
Recursive DFS Implementation
void dfs(int node) {
visited[node] = true;
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
dfs(neighbor);
}
}
}
Conclusion
- Recursion simplifies problems by breaking them into smaller instances.
- Stacks follow LIFO, used in recursive calls and backtracking.
- Queues follow FIFO, useful for breadth-first search (BFS).
- DFS is a fundamental search technique that heavily relies on recursion.
Understanding these concepts is crucial for mastering algorithms and data structures. Try implementing them in competitive programming or problem-solving tasks!
コメント
コメントを投稿