# How the Hanota Problem Demonstrates Divide and Conquer in hello-algo > Explore how the Hanota problem in hello algo showcases divide and conquer. See the code recursively break down disk moving into smaller, manageable steps. - Repository: [Yudong Jin/hello-algo](https://github.com/krahets/hello-algo) - Tags: deep-dive - Published: 2026-02-25 --- **The Hanota (Tower of Hanoi) implementation in the `krahets/hello-algo` repository demonstrates divide and conquer by recursively decomposing the problem of moving `n` disks into three sub-problems: moving `n-1` disks to a buffer, moving the largest disk to the target, and moving the `n-1` disks from the buffer to the target.** The Tower of Hanoi, referred to as the Hanota problem throughout the `hello-algo` codebase, serves as a canonical example of the divide and conquer paradigm in computer science education. This educational repository provides clear, language-agnostic implementations that demonstrate how recursive decomposition solves complex problems by breaking them into smaller, independent sub-problems that are solved and then combined. ## Divide and Conquer Strategy in Hanota The divide and conquer approach consists of three distinct phases that map directly to the Hanota solution structure implemented in the source code. ### Divide Phase In the divide phase, the problem of moving `i` disks is split into three independent sub-problems. According to the implementation in [`hanota.py`](https://github.com/krahets/hello-algo/blob/main/hanota.py), the `dfs()` function handles this decomposition through recursive calls. The first sub-problem moves `i-1` disks from the source peg to the buffer peg, temporarily using the target as auxiliary storage. ### Conquer Phase The conquer phase solves the smallest instances of the problem directly. When `dfs()` encounters the base case where `i == 1`, it executes the `move(src, tar)` operation, transferring a single disk from source to target without further recursion. This direct solution of atomic sub-problems constitutes the conquer step. ### Combine Phase In the combine phase, the solutions to sub-problems are assembled to solve the original problem. The `dfs()` function achieves this implicitly through the ordered sequence of operations: after moving `i-1` disks to the buffer (first sub-problem), moving the largest disk to the target (base case), and moving the `i-1` disks from buffer to target (second sub-problem), the complete solution for `i` disks emerges. ## Source Code Implementation in hello-algo The Python implementation located at [`zh-hant/codes/python/chapter_divide_and_conquer/hanota.py`](https://github.com/krahets/hello-algo/blob/main/zh-hant/codes/python/chapter_divide_and_conquer/hanota.py) (also available in [`en/codes/python/chapter_divide_and_conquer/hanota.py`](https://github.com/krahets/hello-algo/blob/main/en/codes/python/chapter_divide_and_conquer/hanota.py)) provides a concrete realization of this algorithm. The core logic resides in the `dfs()` function, which implements the three-step divide and conquer pattern: ```python def dfs(i: int, src: list[int], buf: list[int], tar: list[int]): """Solve the Hanota sub-problem f(i)""" if i == 1: # base case – conquer move(src, tar) return # divide: three sub-problems dfs(i - 1, src, tar, buf) # f(i‑1) → move top i‑1 disks to buffer move(src, tar) # f(1) → move largest disk to target dfs(i - 1, buf, src, tar) # f(i‑1) → move i‑1 disks from buffer to target ``` The entry point `solve_hanota()` initializes the process by determining the problem size `n` from the length of the source list and invoking `dfs(n, A, B, C)`: ```python def solve_hanota(A: list[int], B: list[int], C: list[int]): n = len(A) # problem size = number of disks dfs(n, A, B, C) # start recursive divide‑and‑conquer ``` ## Cross-Language Implementations The hello-algo repository maintains consistent divide and conquer implementations across multiple languages, demonstrating the paradigm's language-agnostic nature: - **TypeScript**: [`en/codes/typescript/chapter_divide_and_conquer/hanota.ts`](https://github.com/krahets/hello-algo/blob/main/en/codes/typescript/chapter_divide_and_conquer/hanota.ts) implements the same recursive `dfs()` structure with type-safe arrays. - **Rust**: [`en/codes/rust/chapter_divide_and_conquer/hanota.rs`](https://github.com/krahets/hello-algo/blob/main/en/codes/rust/chapter_divide_and_conquer/hanota.rs) demonstrates the pattern using vectors and ownership semantics while preserving the three-step decomposition. - **Documentation**: [`en/docs/chapter_divide_and_conquer/hanota_problem.md`](https://github.com/krahets/hello-algo/blob/main/en/docs/chapter_divide_and_conquer/hanota_problem.md) provides the theoretical foundation explaining how the recursive decomposition maps to the divide and conquer framework. ## Summary The Hanota problem in the hello-algo repository exemplifies the divide and conquer paradigm through: - **Recursive decomposition** of moving `n` disks into three manageable sub-problems involving `n-1` disks and single disk moves. - **Base case handling** where the smallest sub-problem (moving one disk) is solved directly without recursion. - **Implicit combination** where the ordered execution of sub-problem solutions automatically constructs the complete answer. - **Language-agnostic implementation** across Python, TypeScript, Rust, and other languages in the repository. ## Frequently Asked Questions ### What is the Hanota problem? The Hanota problem, commonly known as the Tower of Hanoi, is a classic mathematical puzzle where the objective is to move a stack of disks from a source peg to a target peg following specific rules: only one disk can be moved at a time, and a larger disk cannot be placed on top of a smaller one. The problem serves as a fundamental example of recursive problem-solving in computer science education. ### How does the recursive solution work in the hello-algo implementation? The recursive solution works by treating the problem of moving `i` disks as three sequential operations: first, recursively moving `i-1` disks to a buffer peg; second, moving the largest remaining disk directly to the target; and third, recursively moving the `i-1` disks from the buffer to the target. The recursion terminates when `i == 1`, at which point the `dfs()` function executes a direct move operation without further recursive calls. ### Why is Tower of Hanoi considered a divide and conquer algorithm? Tower of Hanoi qualifies as divide and conquer because it decomposes the original problem of size `n` into smaller sub-problems of size `n-1`, solves each sub-problem recursively using the same algorithm (conquer), and combines the results by executing the sub-problem solutions in a specific order that yields the complete solution. This three-phase structure—divide, conquer, and combine—matches the formal definition of the divide and conquer paradigm. ### Where can I find the Hanota implementation in the hello-algo repository? You can find the Hanota implementation in the chapter dedicated to divide and conquer algorithms. The Python version resides at [`zh-hant/codes/python/chapter_divide_and_conquer/hanota.py`](https://github.com/krahets/hello-algo/blob/main/zh-hant/codes/python/chapter_divide_and_conquer/hanota.py) or [`en/codes/python/chapter_divide_and_conquer/hanota.py`](https://github.com/krahets/hello-algo/blob/main/en/codes/python/chapter_divide_and_conquer/hanota.py), with equivalent implementations available in TypeScript at [`en/codes/typescript/chapter_divide_and_conquer/hanota.ts`](https://github.com/krahets/hello-algo/blob/main/en/codes/typescript/chapter_divide_and_conquer/hanota.ts) and Rust at [`en/codes/rust/chapter_divide_and_conquer/hanota.rs`](https://github.com/krahets/hello-algo/blob/main/en/codes/rust/chapter_divide_and_conquer/hanota.rs). The accompanying documentation explaining the algorithmic concepts is located at [`en/docs/chapter_divide_and_conquer/hanota_problem.md`](https://github.com/krahets/hello-algo/blob/main/en/docs/chapter_divide_and_conquer/hanota_problem.md).