This project explores recursive pathfinding as a structural constraint rather than a stylistic choice. The goal was not simply to traverse nested data, but to design an algorithm whose control flow is itself recursive, placing sustained pressure on the call stack while still remaining correct and tractable.

The distinction between performing a task recursively and being recursive at the code level became central to the design. In this case, the pathfinding algorithm executes recursively at each step of traversal, making stack behavior, recursion depth, and backtracking explicit design concerns rather than incidental implementation details.

Implementation and Design

The system models a rover navigating a terrain map composed of multiple tile types, only one of which is traversable. To support deep traversal without relying on excessive memory overhead, the world is represented as a grid of regions rather than a flat tile map. Each region contains a 4×4 block of tiles and is stored as a single 32-bit unsigned integer using bit packing, allowing sixteen tiles to be encoded compactly while preserving all required state.

This representation makes it possible to work with large maps while keeping memory usage predictable. However, data compaction alone is insufficient when recursion depth reaches hundreds or thousands of calls. To address this, the algorithm enforces a configurable recursion limit. When that limit is reached, the call stack unwinds into an explicit container that preserves traversal state, allowing execution to continue using non-recursive backtracking until recursion can safely resume.

This hybrid approach preserves recursive semantics while avoiding stack overflow, without requiring changes to the system stack size.

Objectives

The primary objectives were to implement a genuinely recursive pathfinding algorithm, aggressively reduce memory footprint through bit packing, and prevent stack overflow under deep traversal conditions. An additional goal was to optimize traversal behavior while maintaining correctness, without relying on non-recursive control flow as the primary mechanism.

Challenges and Outcomes

A key challenge involved validating assumptions about traversal efficiency. While intuition suggested certain instruction sequences would minimize search time, those assumptions had to be verified empirically through testing rather than accepted at face value.

Beyond that, the project was largely a matter of disciplined execution rather than problem discovery. Most complexity arose from managing recursion depth and state transitions cleanly, rather than from unexpected algorithmic failures.

Results

The final implementation successfully navigates large, obstacle-rich maps using a recursive search strategy without triggering stack overflows, regardless of map size or path length. Bit-packed region storage significantly reduced memory overhead, and the controlled stack-unwinding mechanism allowed deep traversal without sacrificing correctness.

If revisited, the core structure would remain unchanged. Any further optimization would likely require abandoning recursion entirely, at which point the problem would become fundamentally different rather than an extension of this approach.