关于此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 shadowed定义。因此，对内部f右侧的fun f(x) = if ...的任何引用都被遮盖，因为fun启用了自递归。并且内部f-in中对end的任何引用均已阴影

---

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

  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的引用是外部f，而不是定义的f，因为val不是自递归定义。因此，在该定义内对f的任何引用都必须取决于外部范围中是否可用。
  但是g(3)位
  is

  被重写，因为在in-end之间，内部f（现在为g）is阴影。因此，对于fun-val-let的阴影而言，它是in还是end都没有关系。

• （还有一些详细信息，val rec和我尚未详细说明的let val f = ...的确切范围。

---

关于您的问题，

1. 您现在应该可以回答这个问题。提供答案的一种不错的方法是：1）为了更清晰起见，对内部函数进行重命名； 2）使用替换手动评估代码（每行重写一次，~>表示重写，因此在这里我不是SML运算符） 。

   这是我的

   second

   示例（不是您的代码）的外观示例：

      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. 什么是尾递归？提供一个定义，并询问您的代码是否满足该定义。

我不确定使用静态/动态分配重写它的意思。您必须详细说明。