在 SML 中 - 如果遇到第一个表达式，为什么简单递归不总是返回 0？

Question

在一个简单的递归中，第一个 if 表达式为真然后为 0。如果递归中的步骤一直进行到第一个表达式为真，为什么不总是返回 0？

fun stepping (n  :  int, number  :  int)  = 
     if number > n
     then 0
     else   1 + stepping (n, number + 1)

函数步进似乎应该在数字上加一，直到数字 > n，然后总是返回 0。相反，它返回你经历递归循环直到数字大于 n 的次数。

上面的代码在 SML 中测试良好，并给了我想要的东西——步数递增 1，直到输入“number”大于输入“n”。但是手动遍历递归步骤，当递增的“数字”> 输入“n”时，返回值似乎始终为 0。我错过了什么？

Answer 1

我认为您将递归链中对

stepping

的最终调用的结果（始终为零）误认为是表达式返回的最终值，但事实并非如此。它实际上是构成整体返回值的更大等式的一部分。

例如，如果我们在评估

stepping(3, 1)

时查看表达式是如何在每次递归调用时构建的，您最终会得到...

result = stepping(3, 1)
result = 1 + stepping(3, 2)
result = 1 + 1 + stepping(3, 3)
result = 1 + 1 + 1 + stepping(3, 4)
result = 1 + 1 + 1 + 0
result = 3

Answer 2

比方说，我今年要给你一些钱，按照这个方案：

• 一月一日你什么都得不到
• 在所有其他日子里，你得到的比我前一天给你的多一美元

今天 2 月 20 日我要付给你多少钱？
五十美元还是什么都没有？
如果你倒着看日历，你最终会到达 1 月 1 日，支付为零，那么你会期望一无所获吗？

回答您的直接问题：如果满足第一个条件，函数does总是返回0——即

if number > n

。

但是，如果不满足第一个条件 –

number <= n

– 它不会返回 0 而是

1 + stepping (n, number + 1)

.
它的工作方式与您调用具有不同名称的函数完全一样；该函数计算一个值，然后该函数加 1.

这 not 就像从循环内部返回一个值，例如（伪代码）

while (true)
{
    if number > n
        return 0
    else 
        number = number +1
}

这也许是你在想什么。