递归返回结果

Question

我正在尝试解决需要计算二叉表达式树的值的问题。

tree_calc(Tree, Eval)

其中 Eval 应包含最终结果，并且 Tree 必须采用以下形式：

tree(LeftNode, Operator, RightNode)

如果我按照上面的形式创建 tree 函数，如果没有空变量来存储结果，我应该如何将计算结果传递给递归？

我的理解是总是需要一个额外的变量来存储结果。

提前致歉，因为我确信我误解了一些基本的东西。

感谢您的帮助。

Answer 1

在这种情况下，tree 不是您所说的函数，也不是 Prolog 所说的谓词。 tree(LeftNode, Operator, RightNode) 只是一个 term 用作表示树的结构。因此，例如，(2 + 3) * 4 将由 tree(tree(2,+,3), *, 4) 表示。您可以使用 tree_calc(tree(tree(2,+,3),*,4), Eval) 调用谓词并期望该查询产生 Eval = 20。在这种情况下，术语 tree/3 不包含结果。

为了举例说明如何在谓词中访问 tree/3，这里有一个简单的谓词，它计算最简单的树（因此没有递归到树叶）：

tree_calc(tree(L, Op, R), E) :-
    % Neither L or R are of the form `tree/3`
    compute(Op, L, R, E).

compute(+, L, R, E) :- E is L + R.
compute(*, L, R, E) :- E is L * R.
compute(-, L, R, E) :- E is L - R.
compute(/, L, R, E) :- E is L / R.

你可以概括compute/4:

compute(Op, L, R, E) :-
    Exp =.. [Op, L, R],
    E is Exp.

你可以这样称呼它：

| ?- tree_calc(tree(2,+,3), Eval).

Eval = 5

yes

对于更一般的情况，您需要检查 L 和 R 以查看它们本身是否是 tree/3 结构并递归调用 tree_calc如果是的话。

Prolog 擅长匹配术语模式。因此，如果您检查联合 L = tree(LL, Op, LR) 并且它成功，这意味着 L 是一个 tree，具有左分支 LL、操作 Op 和右分支 [=32] =].您可以在 Prolog 提示符下尝试这种行为，看看它是如何工作的：

| ?- Tree = tree(2, +, 3), Tree = tree(L, Op, R).

L = 2
Op = (+)
R = 3
Tree = tree(2,+,3)

yes
| ?- Tree = tree(2,+,tree(3,*,4)), Tree = tree(L, Op, R).

L = 2
Op = (+)
R = tree(3,*,4)
Tree = tree(2,+,tree(3,*,4))

yes

| ?- Tree = tree(2,+,tree(3,*,4)), Tree = tree(L, Op, R), R = tree(LR, OpR, RR).

L = 2
LR = 3
Op = (+)
OpR = (*)
R = tree(3,*,4)
RR = 4
Tree = tree(2,+,tree(3,*,4))

yes
| ?-

递归返回结果

Returning results in recursion

binary-tree

prolog