SML中简单递归为何不总是返回0？递归逻辑疑问

先看你写的函数代码：

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

你觉得number>n时返回0，所以函数应该始终返回0，这是因为你只关注了递归的终止条件返回值，却忽略了递归调用的回溯累加过程。

拿具体数值推演就能明白：比如设n=3，number=1：

1. 调用stepping(3,1)：1不大于3，执行1 + stepping(3,2)
2. 调用stepping(3,2)：2不大于3，执行1 + stepping(3,3)
3. 调用stepping(3,3)：3不大于3，执行1 + stepping(3,4)
4. 调用stepping(3,4)：4>3，触发终止条件，返回0

现在开始回溯计算：

• 第3步的结果是1 + 0 = 1
• 第2步的结果是1 + 1 = 2
• 第1步的结果是1 + 2 = 3

最终返回的3，正好是从1递增到4（超过3）需要的3次递增操作次数。

你误区的核心是：终止条件返回的0只是最底层的“基础值”，每一层递归都会把这个值加上1后传递给上层，最终累加的总和就是递增的总次数，而不是直接返回终止条件的0。

内容的提问来源于stack exchange，提问作者DAVID BRYANT