递归函数的堆栈实现

Question

我想用深度优先搜索来实现递归回溯功能，却陷入了需要知道我之前在矩阵中的位置的困境。

我的想法是这样的。我有一个二维数组的矩阵 这就是我的函数：

标记当前的点,如果这个点是我要找的,我就把矩阵中的点设置为解决方案的一部分,把所有之前标记的点也设置为解决方案的一部分.否则,我就调用这个函数到一个有效的相邻点.

问题是第三种情况：如果没有有效的相邻点，那么我需要将该点标记为错误的点，并将函数调用到我之前的位置。要做到这一点，我想我需要一个堆栈来跟踪我之前的移动，但我很难想出如何在f#中做到这一点。

let rec  solve (x,y) =

         mark (x,y)

         if (x,y) = pointimlookingfor then
           for x in 0.. array width-1 do
               for y in 0..array height-1 do
                   if Myarray.[x,y]=markedpoint then
                      Myarray.[x,y]<-partofsolution

         else if (List.isEmpty(adjacentslist) then
              Myarray.[x,y]<-wrong point
              solve (the previous visited point)

         else 
              for (adjacentpoint) in adjacentslist do
                   solve(adjacentpoint)

有什么好办法吗？

Answer 1

在大多数函数式语言中，默认的列表类型是一个不可改变的linked-list，你可以把它作为一个简单的栈，因为它的构造。

cons 是推入堆栈，而 head 是pop from stack.有了这个，我们就可以写一个简单的栈模块。

module Stack =
    let empty = []
    let push item stack = item::stack
    let pop = function
    | [] -> failwith "No items in stack"
    | x::xs -> xs
    let peek stack = stack |> List.tryHead

所以，我们可以写一个简单的堆栈模块。

Stack.empty |> Stack.push 1 |> Stack.push 2 |> Stack.pop |> Stack.pop = Stack.empty //true

在实际操作中，不需要显式地使用上面这样的函数，最简单的方法是在一些累加器上使用模式匹配，当你进行递归折叠时，这些累加器是你随身携带的。

举个例子，让我们重新创建一个堆栈的经典用例-- 平衡括号. 每次遇到开括号，就推到堆栈，遇到收括号，就从堆栈里弹出来，看是否和上次推进去的那个相符。如果不符合，就是不平衡。

let rec isBalanced stack = function
| '(' | '{' | '[' as opened -> opened::stack //push into stack
| ')' | '}' | ']' as closed -> 
    match stack with
    | opened::rest as all -> //pop from stack
        match opened, closed with
        | '(', ')' 
        | '{', '}' 
        | '[', ']' -> rest
        | _ -> failwith "Mismatched braces"
    | [] -> failwith "Closing before open"
| _ -> stack

"abc() { [ 1; 2; 3] }" |> Seq.fold (isBalanced) [] 

还有更简洁的写法，但这说明了如何用不可变的结构来模拟一个经典的栈。

在你的例子中，你可以把一个(x,y)元组推到堆栈上，然后让算法通过反构它来回溯。(x,y)::tail.