Data Structures and Algorithms : Stack, Recursion – DP & Backtracking

I went to the CPE yesterday and was shocked! The questions were all in English and focused entirely on algorithms. Because of this, I’ve decided to start an ‘algorithm journey’ and document my thoughts in English.

Today’s topic is Stacks. While it is a basic data structure, it is also used in some of the most difficult algorithms. Today, I will dive into the stack and explain how it works with a specific algorithm.

Stack

A stack is an Abstract Data Type (ADT) that follows the LIFO (Last-In, First-Out) principle. Because it is an ADT, it can be implemented using different data structures in various programming languages. For example, in Python, we can use a list or linked list to implement a stack, while in C++, we can use thestd::stack container.

  • Python: Using list.append() and list.pop() is the most common way to simulate a stack.
  • C++: Using #include <stack> is highly optimized and preferred.

We can solve the following problems using a Stack:

  • Fibonacci Sequence
  • Tower of Hanoi
  • Maze
  • Eight Queens
  • Infix, Prefix, Postfix

Recursion

the most famous algorithm concept associated with the stack is Recursion. By definition, recursion requires two core components:

  • a self-referential process (a loop-like structure)
  • a base case (the exit condition) to terminate the process

Recursion can be categorized into Direct and Indirect:

  • Direct Recursion : this occurs when a function explicitly calls it self within ite own body.
def Fun():
  ...
  if (...):
    Fun()
  • Indirect Recursion : this occurs when a function calls a second function, which then calls the original function, creating a circular call chain.
def Fun1():
  ...
  if (...):
    Fun2()

def Fun2():
  ...
  if (...):
    Fun1()

Fibonacci Sequence

Fibonacci Sequence is a classical recursion problem defined by the recurrence relation A[n] = A[n-1] + A[n-2].Recursion is most effective when the current solution relies on the result if previously computed subproblems.

def fib(n):
    # Base cases: F(0) = 0, F(1) = 1
    if n <= 1:
        return n
    # Recursive step
    else:
        return fib(n - 1) + fib(n - 2)Code language: PHP (php)

Tower of Hanoi

The Tower of Hanoi is an ancient mathematical puzzle.While the detailed rules are well-known the recursion is the most elegant way to solve it. if you divide the process into sub-step, you will notice the fowlloing pattern:

  • step-1: move the top n-1 disks from Source (Stick 1) to Auxiliary (Stick 2).
  • step-2: move the largest disk n from Source (Stick 1) to Destination (Stick 3).
  • step-3:move the n-1 disks from Auxiliary (Stick 2) to Destination (Stick 3).
def hanoi(n, source, target, auxiliary):
    # Base Case
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    
    # Step 1: move the top n-1 disks
    hanoi(n - 1, source, auxiliary, target)
    
    # Step 2: move the largest disk n
    print(f"Move disk {n} from {source} to {target}")
    
    # Step 3: move the n-1 disks
    hanoi(n - 1, auxiliary, target, source)

hanoi(3, 'A', 'C', 'B')Code language: PHP (php)

Dynamic Programming

DP (Dynamic Programming) is a widely-used method which is based on the Divide-and-Conquer strategy , often implemented using recursion. Nevertheless the DP can slove much more complex problem by recording previous result.

For example, if you use standard recursion to solve the Fibonacci Sequence, the process slows down significantly (or even crashes) when n>100, In contrast, a DP approach remains efficient because it avoids recomputing the same subproblems repeatedly.

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]Code language: JavaScript (javascript)

Backtracking

Backtracking is an advanced algorithm (based on the Enumeration method) that uses recursion to solve problem like the Maze and the Eight Queens. It works by incrementally building a solution and ‘backing-tracking’ (returning to a previous state) as soon as it determines that the current path cannot lead to a valid solution.

Maze

I think everyone has seen Short showing robot races through a maze, how do these robots solve a maze so quickly? The secret is likely Backtracking! (Actually is DFS, but that’s another story)

How is the backtracking implemented int the program? we can examine the process as follows:

def solve_maze(maze, x, y, solution):
    # 1. Base Case
    if x == len(maze) - 1 and y == len(maze[0]) - 1:
        solution[x][y] = 1
        return True

    # 2. Validation: Ensure the current cell is within bounds, not a wall, and unvisited
    if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0 and solution[x][y] == 0:
        # mark the path
        solution[x][y] = 1
        
        # 3. recursion
        if (solve_maze(maze, x + 1, y, solution) or 
            solve_maze(maze, x - 1, y, solution) or 
            solve_maze(maze, x, y + 1, solution) or 
            solve_maze(maze, x, y - 1, solution)):
            return True
        
        # 4. Backtracking: if no direction leads to the exit , unmark this cell
        solution[x][y] = 0
        return False

    return False
# 0 for path, 1 for wall
maze = [
    [0, 1, 0, 0],
    [0, 0, 0, 1],
    [0, 1, 0, 1],
    [0, 0, 0, 0]
]

# Initialize a visited matrix of the same dimensions as the maze.
solution = [[0 for _ in range(len(maze[0]))] for _ in range(len(maze))]

# 從起點 (0, 0) 開始呼叫
if solve_maze(maze, 0, 0, solution):
    print("找到了路徑！")
    for row in solution:
        print(row)
else:
    print("找不到出口。")Code language: PHP (php)

Eight Queens

The Eight Queens puzzle is a classical mathematical problem that is best solved using Backtracking.

placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other.

if you attempted to use Brute Force,it would be nearly impossible! Choosing 8 positions out of 64 results in 4,426,165,368 combinations! However we can simplify the problem by using a key characteristic

each row can only contain exactly one queen.

By dividing the problem into a recursive process, we only need to find a valid column for the queen in each row.

def is_safe(board, row, col):
    # Validation : Checks for column and diagonal conflicts.
    for i in range(row):
        # Check for diagonal conflict: |row_diff| == |col_diff|
        if board[i] == col or abs(board[i] - col) == abs(i - row):
            return False
    return True

def solve_queens(board, row):
    # Base Case
    if row == len(board):
        print(board)
        return True

    for col in range(len(board)):
        if is_safe(board, row, col):
            board[row] = col
            
            # Recursive Step
            solve_queens(board, row + 1)
            
            # Backtracking: Implicitly handled by overwriting board[row] 
            # in the next iteration of the loop.
            
    return False

n = 8
board = [0] * n
solve_queens(board, 0)Code language: PHP (php)

Summarize

Today, I explored the concept of stacks and how recursive algorithms are built upon them. I also analyzed several classic problems that utilize these techniques. However today I have only scratch the surface, Each of the problems we discussed today deserves its own dedicated article. My algorithm journey is just beginning, so… stay tuned!!