将线性递归函数重写为尾递归函数

Question

我想知道,当重写"常规"递归函数作为尾递归函数时,我该如何处理？有某种策略吗？

例如:我有这个简单的函数,我想把它变成一个尾递归的函数:

int rec(int n) {
    if (n % 2 || n > 10) {
    return n;
    }
    return  rec(n+1) + rec(n+2);
}

任何帮助表示赞赏.

Answer 1

答案取决于你对"尾递归"函数的定义和"重写"函数的定义,但我将假设大致非正式的理解:

• 没有原始版本中没有的迭代.
• 没有显式的堆栈/数组/等.那些不是原始版本.
• 除了尾递归之外没有递归调用(意思是,调用是语句中的整个表达式return).
• 辅助函数是可以的,但相互递归不是.
• 由诸如整数溢出,堆栈溢出,舍入误差等现实考虑因素引起的非等效性并不重要.

那个不碍事...你应该知道,并不总是能够以尾递归的方式重写函数.你自己的例子具有的功能使2个在非基本情况递归调用,我们显然不能改变两个人是在一个整个表达式return语句,所以唯一的原因,你的例子可以重写为尾递归是我们可以消除其中一个电话.

那么,让我们从你的功能开始:

int rec(int n) {
    if (n % 2 || n > 10) {
        return n;                 // line 3
    }
    return  rec(n+1) + rec(n+2);  // line 5
}

现在,如果n是奇数,那么我们n在第3行返回; 所以如果我们到达第5行,那么我们就知道n必须是均匀的.这意味着如果我们已经到达第5行,那么它n+1就是奇数并且rec(n+1)将会是n+1.所以我们可以消除一个递归调用:

int rec(int n) {
    if (n % 2 || n > 10) {
        return n;
    }
    return (n+1) + rec(n+2);
}

接下来,它有助于扩展一个真实的例子,看看它是什么样的:

rec(6) = 7 + rec(8)
       = 7 + (9 + rec(10))
       = 7 + (9 + (11 + rec(12)))
       = 7 + (9 + (11 + (12)))

一个重要的见解是,由于添加是关联的,我们可以以相反的方式对术语进行分组:

rec(6) = ((7 + 9) + 11) + 12

这很有用,因为它意味着我们可以在继续时计算结果的部分总和,并将其作为单独的参数传递:

int rec(int n, int sum_so_far) {
    if (n % 2 || n > 10) {
        return sum_so_far + n;
    }
    return rec(n+2, sum_so_far + (n+1));
}

...现在我们有一个尾递归函数,但它要求客户传递额外的参数!为了解决这个问题,我们只需将其重命名并将其rec_helper包装在一个函数中,以便客户端调用:

int rec_helper(int n, int sum_so_far) {
    if (n % 2 || n > 10) {
        return sum_so_far + n;
    }
    return rec_helper(n+2, sum_so_far + (n+1));
}

int rec(int n) {
    return rec_helper(n, 0);
}

如您所见,没有一般策略; 相反,我们需要分析函数,并利用有关整数的事实,消除一个递归调用,然后我们需要再次做同样的事情将另一个递归调用转换为尾递归调用.

然而,我们所做的一个方面是一个非常常见的模式,即将递归移动到一个带有附加参数的辅助函数,其中该参数包含到目前为止已计算的部分结果.我会说在构造尾递归函数时,我至少有90%的时间使用此模式.