Informed search

Recursive Best-First Search (RBFS)

A* smarts on a shoestring memory budget.

Interactive demo coming soon — read the theory below

The idea

Recursive Best-First Search (RBFS) tries to be as smart as A* (always chasing the most promising node by f = g + h) while using almost no memory. It dives down the current best-looking path, but keeps one number in its back pocket: the f-value of the best alternative it walked past. The moment the path it's on starts looking worse than that alternative, it backs out, remembers how bad this branch turned out to be, and tries the alternative instead.

How it works

Start at the root with an f-limit of infinity (no ceiling yet). f(n) = g(n) + h(n): cost-so-far plus the heuristic estimate to the goal.
Look at the current node's children and compute each child's f-value.
Pick the child with the smallest f-value — that's the 'best'. Note the second-smallest f-value — that's the best 'alternative'.
Recurse into the best child, but pass down a new limit = min(the limit you were given, the alternative's f-value). This limit says 'don't spend more than this before checking back'.
As you explore deeper, if every path below the best child exceeds the limit, RBFS gives up on it — but first it backs up the smallest f-value it saw down there onto the child (this 'remembered' value is why it won't blindly re-pick a known-bad branch).
Back at the parent, re-sort the children using these updated f-values, then repeat: dive into the new best, bounded by the new best alternative.
Continue until a node that IS a goal is expanded as the best choice — return its path.
If the root's best child exceeds infinity (impossible unless no solution), report failure.

OPEN, CLOSED & the data structures

Almost none — that's the point. There's no big OPEN priority queue and no CLOSED set. State lives in the recursion stack: one stack frame per node on the current path from root to the node being explored. Each frame stores that node's children with their (possibly updated) f-values, plus the incoming f-limit. The single most important piece of state is the 'best alternative f-value' passed as the limit into each recursive call.

Pseudocode

function RBFS(node, f_limit):
    if node is Goal: return SUCCESS, node.path
    children = expand(node)
    if children is empty: return FAILURE, infinity
    for each child in children:
        # f-value never drops below the parent's (pathmax)
        child.f = max(child.g + child.h, node.f)
    loop:
        best = child with lowest f in children
        if best.f > f_limit:
            return FAILURE, best.f          # back up the best f as new estimate
        alternative = second-lowest f among children
        result, best.f = RBFS(best, min(f_limit, alternative))
        if result == SUCCESS:
            return SUCCESS, best.path

At a glance

Complete?Complete on finite graphs with an admissible heuristic — if a solution exists it will be found, because f-limits only ever rise and every reachable branch is eventually retried. (Like most search, it can loop on infinite state spaces.)

Optimal?Optimal — with an admissible heuristic (h never overestimates the true cost), RBFS returns a least-cost path, exactly like A*. It never commits to a goal until that goal is genuinely the cheapest remaining option.

TimeO(b^d)-ish, but worse than A* in practice: because it forgets subtrees when it backtracks, it re-expands the same nodes many times when the best path keeps flip-flopping. Exact count depends heavily on how accurate the heuristic is.

SpaceO(b*d) — linear in the depth of the solution (b = branching factor, d = depth). It only holds the current root-to-node path plus each node's siblings, not the whole frontier. This is its headline advantage over A*.

👍 When to use it

You want A*-quality optimal answers but A* runs out of memory on your problem
The search space is large/deep and holding the full frontier is infeasible
You have a decent admissible heuristic guiding the search
Memory is your bottleneck and you can trade extra CPU time for it

⚠️ Watch out for

Node re-expansion: when two paths have near-equal f-values, RBFS thrashes back and forth and redoes work — it can be far slower than A* even though it visits 'fewer' nodes at once.
The returned 'FAILURE' value isn't a real failure — it's the backed-up f-value used to update the parent. Don't treat it as 'no solution'.
It needs an admissible heuristic for the optimality guarantee; a bad heuristic wrecks both speed and correctness.
Remember to back up (propagate) the best child f-value on retreat — skipping this breaks the 'remember the best alternative' logic entirely.
It's easy to confuse with IDA*: both are linear-space A* variants, but RBFS tracks the best alternative f-value rather than sweeping a single global cost threshold.