棘手的递归（尾部）函数示例

Question

我从来不喜欢玩定义，尤其是在面试时。据我所知:

编辑：

尾递归函数是在递归调用后不再进行任何计算的函数。

我认为第二个不是尾递归，因为它根本不进行递归调用，因此不是尾递归。

但是第一个是尾递归的，即使它进行了 2 次递归调用，之后它什么也没做，所以我想我在这里正确使用了我对尾递归的定义。

let rec func x =
    if x > 10 then x else func (func (x+1))  

let f a b = a + b

Answer 1

您对递归函数的定义是 tail 递归函数。递归函数简单地定义为在执行过程中的某个时刻调用自身的函数。该定义还允许间接递归的函数，即它们调用另一个函数再次调用原始函数（其中此链可以是任意长度）。

你认为你的第二个函数根本不是递归的，这是对的。但是，第一个函数不是尾递归。

如果我们将此函数移至 Scala，我们将得到；

@tailrec
def func(x: Int): Int = 
{
    if (x > 10) x
    else func(func(x+1))
}

@tailrec 注释告诉我们某些东西是否是尾递归的。然而，编译器告诉我们有一个递归调用不在尾部位置。即，两个调用的内部。尾递归函数要求 all 对函数的调用都在尾部位置，而不仅仅是最终调用在尾部位置

Tricky recursive (tail) function examples