recursion - 关于这个sml递归函数的几个问题

Question

1. 什么时候f(x-1)被调用，是调用f(x) = x+10还是f(x) = if ...
2. 这是尾递归吗？

3. 我应该如何使用静态/动态分配重写它？

   let fun f(x) = x + 10
   in
       let fun f(x) = if x < 1 then 0 else f(x-1)
       in f(3)
       end
   end
   

Answer 1

在解决您的问题之前，以下是对您的代码的一些观察：

• 有两个功能f，一个在另一个里面。他们彼此不同。

• 为了减少这种混淆，您可以将内部函数重命名为g：

  let fun f(x) = x + 10
  in
      let fun g(x) = if x < 1 then 0 else g(x-1)
      in g(3)
      end
  end
  

• 这通过以下规则清除了哪个函数调用哪个函数：外部f定义在外部in-内部end，但立即被内部隐藏f。f因此，内部右侧的任何引用fun f(x) = if ...都会被遮蔽，因为fun可以实现自递归。f并且对内部的任何引用in-end都被遮蔽

---

• 在下面的切线示例中，如果我们使用而不是，则内部声明的右侧f不会影响外部：fvalfun

  let fun f(x) = if (x mod 2 = 0) then x - 10 else x + 10
  in
      let val f = fn x => f(x + 2) * 2
      in f(3)
      end
  end
  

  如果在第二段代码中将内部f重命名为，它看起来像：g

  let fun f(x) = if (x mod 2 = 0) then x - 10 else x + 10
  in
      let val g = fn x => f(x + 2) * 2
      in g(3)
      end
  end
  

  重要的一点是，该f(x + 2)部分没有被重写，g(x + 2)因为这val意味着对f外部fs 的引用，而不是f被定义的，因为 aval不是自递归定义。因此，对该定义中的任何引用f都必须依赖于它在外部范围内是否可用。

  但是该g(3)位被重写，因为在in-之间end，内部f（现在g）是阴影。因此，对于- -的阴影，无论是 afun还是 aval都无关紧要。letinend

• （还有一些更多的细节。以及我没有详细说明val rec的 a 的确切范围。）let val f = ...

---

至于你的问题，

1. 你现在应该可以回答这个问题了。提供答案的一个好方法是 1) 为清楚起见重命名内部函数，2) 使用替换手动评估代码（每行重写一次，~>表示重写，所以我在这里不是指 SML 运算符）。

   这是我的第二个示例（不是您的代码）的外观示例：

      g(3)
   ~> (fn x => f(x + 2) * 2)(3)
   ~> f(3 + 2) * 2
   ~> f(5) * 2
   ~> (if (5 mod 2 = 0) then 5 - 10 else 5 + 10) * 2
   ~> (if (1 = 0) then 5 - 10 else 5 + 10) * 2
   ~> (5 + 10) * 2
   ~> 15 * 2
   ~> 30
   

   您的手动评估看起来会有所不同，并且可能得出不同的结论。

2. 什么是尾递归？提供定义并询问您的代码是否满足该定义。

3. 我不确定使用静态/动态分配重写它是什么意思。你必须详细说明。