关于此 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遮蔽。因此，对内部fun f(x) = if ...右侧f的任何引用都会被遮蔽，因为fun启用自递归。任何对内inf的引用——end都是阴影

---

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

  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，因为val不是自递归定义。因此，在该定义中对f的任何引用都必须取决于它在外部范围内的可用性。

  但是g(3)位被重写了，因为在in-end之间，内f(现在g(是阴影的。因此，无论是fun还是val对于let-in-end的阴影无关紧要。

• (还有一些细节。val rec以及我尚未详细说明的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. 我不确定使用静态/动态分配重写它是什么意思。你必须详细说明。