The problem of unbounded trees can be alleviated by supplying DFS with predetermined depth limit L. that is, nodes at depth L are treated as if they have no successors. This approach is called depth limited search. The depth limit solves the infinite path problem.

Unfortunately, it also introduces an additional source of incompleteness if we choose l < d , that is, the shallowest goal is beyond the depth limit. Depth limited search will also be non optimal if we choose l > d. its time complexity is $O(b^l)$ and its space complexity is O(bl).

DLS can be implemented as a simple modification or the general tree search algorithm or the recursive DFS algo. We show the pseudo code for recursive DLS in figure (9). Notice that DLS can terminate with two kinds of failure: The standard failure, and value indicates no solution, The cut off value indicates no solution within the depth limit.

a solution, or failure/cutoff

function DEPTH – LIMITED – SEARCH (problem, limit) returns

return RECURSIVE – DLS (MAKE – NODE (INITIAL – STATE

[problem]), problem, limit)

or failure/cutoff

function RECURSIVE – DLS (node, problem, limit) returns a solution,

cutoff – occurred? $\leftarrow$ false

if GOAL – TEST [problem] (state [node]) then return

else for each successor in EXPAND (node, problem) do

result $\leftarrow$ RECURSIVE – DLS (successor, problem, limit)

if result = cutoff then cutoff occurred? $\leftarrow$ true

else if result $\neq$ failure then return result

if cutoff occurred? then return cutoff else return failure.

Figure (9) A recursive implementation of DLS.