Depth-Limited Search Recursive Pseudocode

Question

I'm looking at a pseudocode implementation of Depth-Limited Search, and I'm having trouble understanding it.

The pseudocode is:

Function Recursive-DLS(node, problem, limit)
    cutoff-occurred? = false
    if Goal-Test(problem, State[node]) then return node
    else if Depth[node] = limit then return cutoff
    else for each successor in Expand(node, problem) do
            result = Recursive-DLS(successor, problem, limit-1) 
            if result = cutoff then cutoff-occurred? = true
            else if result != failure then return result        
    if cutoff-occurred? then return cutoff else return failure

Im mainly having trouble understanding the reason for recurring the algo with limit-1 for every successor. Can someone run through this with me? Some graphical explanation would be nice haha.

I'm going to look at other sources in the meantime. Thanks for reading!

Answer 1

The pseudo-code appears to be wrong. (It's actually possible for the base case to never be encountered if the node depth/limit values skip eachother - being simultaneously increased and decreased in each recursive call.)

The recursive case was written with the limit - 1 so a base case can be reached (instead of "limit", think "remaining").

However, the base case for the limit is if Depth[node] = limit then return cutoff. Following David Chan's suggestion it should be if 0 = limit then return cutoff, which would agree with the limit - 1 in the recursive case.

Alternatively, just pass limit in the recursive case and leave the current base case alone.