{"id":633,"date":"2026-06-15T11:43:00","date_gmt":"2026-06-15T11:43:00","guid":{"rendered":"https:\/\/hyc.eshachem.com\/program\/?page_id=633"},"modified":"2026-06-15T11:45:25","modified_gmt":"2026-06-15T11:45:25","slug":"data-structures-and-algorithms-stack-recursion-dp-backtracking","status":"publish","type":"page","link":"https:\/\/hyc.eshachem.com\/program\/technical-articles\/data-structures-and-algorithms-stack-recursion-dp-backtracking\/","title":{"rendered":"Data Structures and Algorithms\u00a0: Stack, Recursion – DP & Backtracking"},"content":{"rendered":"\n

I went to the CPE yesterday and was shocked! The questions were all in English and focused entirely on algorithms. Because of this, I\u2019ve decided to start an \u2018algorithm journey\u2019 and document my thoughts in English.<\/p>\n\n\n\n

Today\u2019s topic is Stacks<\/strong>. While it is a basic data structure, it is also used in some of the most difficult<\/strong> algorithms. Today, I will dive into<\/strong> the stack and explain how it works with a specific algorithm.<\/p>\n\n\n\n

Stack<\/h3>\n\n\n\n

A stack is an Abstract Data Type (ADT)<\/strong> that follows the LIFO (Last-In, First-Out)<\/strong> 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<\/strong><\/code> <\/strong>or linked list<\/strong><\/code> <\/strong>to implement a stack, while in C++, we can use thestd::stack<\/strong><\/code> container.<\/p>\n\n\n\n

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

    We can solve the following problems using a Stack<\/strong>:<\/p>\n\n\n\n

      \n
    • Fibonacci Sequence<\/strong><\/li>\n\n\n\n
    • Tower of Hanoi<\/strong><\/li>\n\n\n\n
    • Maze<\/strong><\/li>\n\n\n\n
    • Eight Queens<\/strong><\/li>\n\n\n\n
    • Infix, Prefix, Postfix<\/strong><\/li>\n<\/ul>\n\n\n\n

      Recursion<\/h3>\n\n\n\n

      the most famous algorithm concept associated with the stack is Recursion<\/strong>. <\/strong>By definition, recursion requires two core components:<\/p>\n\n\n\n

        \n
      • a self-referential process<\/strong> (a loop<\/strong>-like structure)<\/li>\n\n\n\n
      • a base case<\/strong> (the exit <\/strong>condition) to terminate the process<\/li>\n<\/ul>\n\n\n\n

        Recursion can be categorized into Direct <\/strong>and Indirect<\/strong>:<\/p>\n\n\n\n

          \n
        • Direct Recursion<\/strong>\u00a0: this occurs when a function explicitly calls it self within ite own body.<\/li>\n<\/ul>\n\n\n
          def Fun():\n  ...\n  if (...):\n    Fun()<\/code><\/span><\/pre>\n\n\n
            \n
          • Indirect Recursion\u00a0: <\/strong>this occurs when a function calls a second function, which then calls the original function, creating a circular call chain.<\/li>\n<\/ul>\n\n\n
            def Fun1():\n  ...\n  if (...):\n    Fun2()\n\ndef Fun2():\n  ...\n  if (...):\n    Fun1()<\/code><\/span><\/pre>\n\n\n
            Fibonacci S<\/strong>equence<\/h4>\n\n\n\n
            Fibonacci Sequence is a classical recursion problem defined by the recurrence relation A[n] = A[n-1] + A[n-2]<\/code>.Recursion is most effective <\/strong>when the current solution relies on the result if previously computed subproblems.<\/p>\n\n\n
            def fib(n):\n    # Base cases: F(0) = 0, F(1) = 1<\/span>\n    if<\/span> n <= 1<\/span>:\n        return<\/span> n\n    # Recursive step<\/span>\n    else<\/span>:\n        return<\/span> fib(n - 1<\/span>) + fib(n - 2<\/span>)<\/code><\/span>Code language:<\/span> PHP<\/span> (<\/span>php<\/span>)<\/span><\/small><\/pre>\n\n\n
            Tower of\u00a0Hanoi<\/h4>\n\n\n\n
            \"\"<\/figure>\n\n\n\n
            The Tower of Hanoi is an ancient <\/strong>mathematical puzzle.While the detailed rules are well-known the recursion is the most elegant <\/strong>way to solve it. if you divide the process into sub-step, you will notice the fowlloing pattern:<\/p>\n\n\n\n
              \n
            • step-1: move the top n-1<\/code> disks from Source<\/strong> (Stick 1) to Auxiliary<\/strong> (Stick 2).<\/li>\n\n\n\n
            • step-2: move the largest disk n<\/code> from Source<\/strong> (Stick 1) to Destination<\/strong> (Stick 3).<\/li>\n\n\n\n
            • step-3:move the n-1<\/code> disks from Auxiliary<\/strong> (Stick 2) to Destination<\/strong> (Stick 3).<\/li>\n<\/ul>\n\n\n
              def hanoi(n, source, target, auxiliary):\n    # Base Case<\/span>\n    if<\/span> n == 1<\/span>:\n        print<\/span>(f\"Move disk 1 from {source} to {target}\"<\/span>)\n        return<\/span>\n    \n    # Step 1: move the top n-1 disks<\/span>\n    hanoi(n - 1<\/span>, source, auxiliary, target)\n    \n    # Step 2: move the largest disk n<\/span>\n    print<\/span>(f\"Move disk {n} from {source} to {target}\"<\/span>)\n    \n    # Step 3: move the n-1 disks<\/span>\n    hanoi(n - 1<\/span>, auxiliary, target, source)\n\nhanoi(3<\/span>, 'A'<\/span>, 'C'<\/span>, 'B'<\/span>)<\/code><\/span>Code language:<\/span> PHP<\/span> (<\/span>php<\/span>)<\/span><\/small><\/pre>\n\n\n
              Dynamic Programming<\/h3>\n\n\n\n
              DP (Dynamic Programming)<\/strong> is a widely-used method which is based on the Divide-and-Conquer<\/strong> strategy\u00a0, often implemented using recursion. Nevertheless the DP can slove much more complex problem by recording previous result<\/strong>.<\/p>\n\n\n\n
              For example, if you use standard recursion to solve the Fibonacci Sequence<\/strong>, the process slows down significantly (or even crashes) when n>100<\/code>, In contrast, a DP approach remains efficient <\/strong>because it avoids recomputing<\/strong> the same subproblems repeatedly.<\/p>\n\n\n
              def fib_memo(n, memo={}):\n    if<\/span> n in<\/span> memo:\n        return<\/span> memo[n]\n    if<\/span> n <= 1<\/span>:\n        return<\/span> n\n    \n    memo[n] = fib_memo(n - 1<\/span>, memo) + fib_memo(n - 2<\/span>, memo)\n    return<\/span> memo[n]<\/code><\/span>Code language:<\/span> JavaScript<\/span> (<\/span>javascript<\/span>)<\/span><\/small><\/pre>\n\n\n
              Backtracking<\/strong><\/h3>\n\n\n\n
              Backtracking <\/strong>is an advanced <\/strong>algorithm (based on the Enumeration method)<\/strong> that uses recursion to solve problem like the Maze<\/strong> and the Eight Queens<\/strong>. It works by incrementally building a solution and \u2018backing-tracking\u2019 <\/strong>(returning to a previous state) as soon as it determines that the current path cannot lead to a valid solution.<\/p>\n\n\n\n
              Maze<\/h4>\n\n\n\n
              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<\/strong>! (Actually is DFS, but that\u2019s another story)<\/p>\n\n\n\n
              How is the backtracking implemented int the program? we can <\/strong>examine the process as follows:<\/strong><\/p>\n\n\n
              def solve_maze(maze, x, y, solution):\n    # 1. Base Case<\/span>\n    if<\/span> x == len(maze) - 1<\/span> and<\/span> y == len(maze[0<\/span>]) - 1<\/span>:\n        solution[x][y] = 1<\/span>\n        return<\/span> True<\/span>\n\n    # 2. Validation: Ensure the current cell is within bounds, not a wall, and unvisited<\/span>\n    if<\/span> 0<\/span> <= x < len(maze) and<\/span> 0<\/span> <= y < len(maze[0<\/span>]) and<\/span> maze[x][y] == 0<\/span> and<\/span> solution[x][y] == 0<\/span>:\n        # mark the path<\/span>\n        solution[x][y] = 1<\/span>\n        \n        # 3. recursion<\/span>\n        if<\/span> (solve_maze(maze, x + 1<\/span>, y, solution) or<\/span> \n            solve_maze(maze, x - 1<\/span>, y, solution) or<\/span> \n            solve_maze(maze, x, y + 1<\/span>, solution) or<\/span> \n            solve_maze(maze, x, y - 1<\/span>, solution)):\n            return<\/span> True<\/span>\n        \n        # 4. Backtracking: if no direction leads to the exit , unmark this cell<\/span>\n        solution[x][y] = 0<\/span>\n        return<\/span> False<\/span>\n\n    return<\/span> False<\/span>\n# 0 for path, 1 for wall<\/span>\nmaze = [\n    [0<\/span>, 1<\/span>, 0<\/span>, 0<\/span>],\n    [0<\/span>, 0<\/span>, 0<\/span>, 1<\/span>],\n    [0<\/span>, 1<\/span>, 0<\/span>, 1<\/span>],\n    [0<\/span>, 0<\/span>, 0<\/span>, 0<\/span>]\n]\n\n# Initialize a visited matrix of the same dimensions as the maze.<\/span>\nsolution = [[0<\/span> for<\/span> _ in range(len(maze[0<\/span>]))] for<\/span> _ in range(len(maze))]\n\n# \u5f9e\u8d77\u9ede (0, 0) \u958b\u59cb\u547c\u53eb<\/span>\nif<\/span> solve_maze(maze, 0<\/span>, 0<\/span>, solution):\n    print<\/span>(\"\u627e\u5230\u4e86\u8def\u5f91\uff01\"<\/span>)\n    for<\/span> row in solution:\n        print<\/span>(row)\nelse<\/span>:\n    print<\/span>(\"\u627e\u4e0d\u5230\u51fa\u53e3\u3002\"<\/span>)<\/code><\/span>Code language:<\/span> PHP<\/span> (<\/span>php<\/span>)<\/span><\/small><\/pre>\n\n\n
              Eight Queens<\/strong><\/h4>\n\n\n\n
              The Eight Queens puzzle is a classical mathematical problem that is best solved using Backtracking<\/strong>.<\/p>\n\n\n\n
              \n
              placing eight chess queens on an 8\u00d78 chessboard so that no two queens threaten each\u00a0other.<\/p>\n<\/blockquote>\n\n\n\n
              if you attempted to use Brute Force<\/strong>,it would be nearly impossible! Choosing 8 positions out of 64 results in 4,426,165,368<\/strong> combinations! However we can simplify the problem by using a key characteristic<\/p>\n\n\n\n
              \n
              each row can only contain exactly one queen<\/strong>.<\/p>\n<\/blockquote>\n\n\n\n
              By dividing the problem into a recursive process, we only need to find a valid column for the queen in each row.<\/p>\n\n\n
              def is_safe(board, row, col):\n    # Validation : Checks for column and diagonal conflicts.<\/span>\n    for<\/span> i in range(row):\n        # Check for diagonal conflict: |row_diff| == |col_diff|<\/span>\n        if<\/span> board[i] == col or<\/span> abs(board[i] - col) == abs(i - row):\n            return<\/span> False<\/span>\n    return<\/span> True<\/span>\n\ndef solve_queens(board, row):\n    # Base Case<\/span>\n    if<\/span> row == len(board):\n        print<\/span>(board)\n        return<\/span> True<\/span>\n\n    for<\/span> col in range(len(board)):\n        if<\/span> is_safe(board, row, col):\n            board[row] = col\n            \n            # Recursive Step<\/span>\n            solve_queens(board, row + 1<\/span>)\n            \n            # Backtracking: Implicitly handled by overwriting board[row] <\/span>\n            # in the next iteration of the loop.<\/span>\n            \n    return<\/span> False<\/span>\n\nn = 8<\/span>\nboard = [0<\/span>] * n\nsolve_queens(board, 0<\/span>)<\/code><\/span>Code language:<\/span> PHP<\/span> (<\/span>php<\/span>)<\/span><\/small><\/pre>\n\n\n
              Summarize<\/h3>\n\n\n\n
              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, <\/strong>Each of the problems we discussed today deserves its own dedicated article<\/strong>. My algorithm journey <\/strong>is just beginning, so\u2026 stay tuned!!<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"
              I went to the CPE yesterday and was shocked! The questions were all in English and focused entirely on algorithms. Because of this, I\u2019ve decided to start an \u2018algorithm journey\u2019 and document my thoughts in English. Today\u2019s topic is Stacks. While it is a basic data structure, it is also used in some of the […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":440,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"class_list":["post-633","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/hyc.eshachem.com\/program\/wp-json\/wp\/v2\/pages\/633","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/hyc.eshachem.com\/program\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/hyc.eshachem.com\/program\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/hyc.eshachem.com\/program\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/hyc.eshachem.com\/program\/wp-json\/wp\/v2\/comments?post=633"}],"version-history":[{"count":2,"href":"https:\/\/hyc.eshachem.com\/program\/wp-json\/wp\/v2\/pages\/633\/revisions"}],"predecessor-version":[{"id":635,"href":"https:\/\/hyc.eshachem.com\/program\/wp-json\/wp\/v2\/pages\/633\/revisions\/635"}],"up":[{"embeddable":true,"href":"https:\/\/hyc.eshachem.com\/program\/wp-json\/wp\/v2\/pages\/440"}],"wp:attachment":[{"href":"https:\/\/hyc.eshachem.com\/program\/wp-json\/wp\/v2\/media?parent=633"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}