AI Glossary / Graphs and symbolic AI / Advanced

Recursive best-first search

Definition

Recursive best-first search, or RBFS, is a heuristic search algorithm that pursues promising paths while limiting memory use. It recursively explores a branch until another remembered alternative looks better, then backs up and switches. By retaining compact cost information rather than the whole search frontier, it trades repeated computation for a smaller memory requirement.

What it means

Best-first search prefers candidates according to an evaluation score. In an A*-style setup, f = g + h combines the path cost already incurred, g, with an estimate of remaining cost, h. Keeping every promising candidate can require substantial memory.

RBFS addresses that storage problem. It keeps the current recursive path and information about competing successors along that path. When a branch becomes less attractive, its detailed descendants can be discarded while a revised score is remembered. If the branch becomes worth revisiting, its descendants are generated again. The word “recursive” describes this nested exploration and return process, not repeated execution of an entire independent search.

How it works

At a node, generate successors and assign each a score at least as large as both its ordinary g + h value and the backed-up score inherited from its parent. Rank the successors by those scores.

Explore the best successor with a limit determined by the smaller of the current limit and the next-best alternative's score. If the best available score exceeds that limit, return the updated value to the caller. The caller can then reconsider its alternatives using what was learned.

This bookkeeping prevents a forgotten branch from being treated as though its earlier search revealed nothing. It does not preserve every explored state. Implementations must separately consider loops and repeated states; avoiding a state already on the current path is different from maintaining a global table of all explored states.

Three practical examples

• Puzzle solving: a program searches move sequences with a heuristic while avoiding storage of a large explicit frontier.
• Planning experiments: researchers compare how much repeated search is acceptable under a restricted memory budget.
• Route-search teaching: a small weighted tree demonstrates why discovering a worse bound in one branch can make another branch preferable.

Think of it this way

Think of inspecting several possible routes while carrying a small notebook. You follow the route that currently looks cheapest, retain a note about alternatives, and turn back if new information changes their ranking. The analogy is limited: RBFS follows precise numerical limits and backup rules. It is not a traveler improvising a detour, and computational backtracking need not involve physical movement.

Worked example

Use a finite search tree with root S and two children, A and B. Edges S→A and S→B each cost one. A has a single goal child GA reached at additional cost six. B has a single goal child GB reached at additional cost five. Thus the complete routes cost seven and six respectively.

Choose heuristic values h(S)=0, h(A)=3, h(B)=4, and zero at both goals. Initially A has f=1+3=4 and B has f=1+4=5. RBFS first explores A with limit five, reflecting the alternative through B.

Generating GA reveals a score of seven. Because seven exceeds A's limit of five, that recursive call returns without accepting GA, and A's remembered score becomes seven. At S, B now looks better with score five. B is explored with limit seven, and its goal GB has score six, so that goal can be reached and returned.

The answer is S→B→GB with cost six. The initial preference for A was not a commitment. This example has no cycles, and its heuristics underestimate the remaining route costs. The numerical trace illustrates switching and backup rather than claiming a runtime advantage over another algorithm.

Illustrative case study

Fictional case: Alder Search Workshop builds a demonstration planner whose explicit frontier consumes more memory than its teaching environment permits. The team implements RBFS and records both peak stored nodes and the number of regenerated nodes.

On a constructed example, learners see the planner revisit a branch after an alternative becomes less promising. The instructor explains that this repeated work is part of the memory trade-off, not necessarily an implementation error. A separate test includes a cycle so the class can examine the chosen loop-handling policy.

The fictional exercise does not establish that RBFS is fastest for production planning. It demonstrates why memory usage and elapsed work must be evaluated together.

Common misconceptions and mistakes

RBFS is not ordinary depth-first search with a fixed child order. The evaluation scores and competing alternatives control when it continues or backs up.

“Linear space” does not mean constant memory. With bounded branching, storage grows with the maintained search depth; retaining successors also contributes a branching-factor multiplier.

Nor does low memory imply low runtime. Regenerating subtrees can be expensive. Optimality claims also require the appropriate evaluation function and search assumptions. An arbitrary heuristic or weighted score should not inherit an A*-style guarantee merely because it is used inside RBFS.

Business use

RBFS is relevant when the search frontier is a major memory bottleneck and regenerating states is feasible. A useful assessment compares memory, time, repeated expansions, and returned solution cost on representative problems.

Consider the cost of reconstructing a state and evaluating its heuristic. If either is expensive, the storage saving may be offset by repeated work. Also document whether the problem is a tree or a graph, how cycles are handled, and whether the application needs a cheapest solution or an acceptable one within a deadline.

People also ask

Does RBFS remember nothing about abandoned branches?

It remembers backed-up evaluation information, even though detailed descendants may be discarded.

Is its limit a maximum recursion depth?

No. The key limit is an evaluation-cost bound, although recursion depth separately affects memory.

Does it automatically prevent every repeated state?

No. A current-path cycle check does not detect every duplicate reached through a different path. The implementation's policy matters.

Check your understanding

Why does the worked search leave A after generating a goal of cost seven?

Answer: A's current limit is five because B remains an alternative at that score. The new bound makes A less promising, so the search backs up and considers B.

Related terms

• Best-first search
• Heuristic
• Repeated state
• A* search
• path cost
• iterative deepening
• memory-bounded search
• backtracking

Learn next

redraw the worked tree with a different admissible heuristic and trace every limit and backed-up value. Then compare the information retained by RBFS with the explicit frontier retained by ordinary A*.

• Backed-up value
• Admissible heuristic

More in Graphs and symbolic AI

• Record linkage - Record linkage is the process of deciding which records refer to the same real-world entity across or within datasets.
• Rectangular grid - A rectangular grid is a two-dimensional arrangement of locations organized into rows and columns.
• Rectified Linear Unit - A Rectified Linear Unit, usually abbreviated ReLU, is a neural-network activation function defined by ReLU(x) = max(0, x).
• Reduct - A reduct, in stable-model logic programming, is a simplified program constructed relative to a proposed set of true atoms.
• Redundancy - Redundancy, in the supplied bipartite-network context, measures how many pairs of a node's neighbors share another common neighbor.
• Redundant path - A redundant path, in state-space search, is a route to a state that adds no useful advantage over another available route for the search objective.

Sources

Primary sources: AIMA's reference implementation documentation gives the recursive limit and backup rules: https://aimacode.github.io/aima-java/aima3e/javadoc/aima-core/aima/core/search/informed/RecursiveBestFirstSearch.html . Richard Korf's author publication page includes the original linear-space best-first search abstract: https://web.cs.ucla.edu/~korf/publications.html . The tree, trace, and fictional case are original.

Previous: Recurrent state space model Next: Recursive feature elimination