设 m、n 为正整数,
mn 等于 0 时,函数f(m, n) 等于 m + n + 1,f(m, n) 等于 f(m - 1, f(m, n - 1))。下面是上述问题的一段简单代码(Javascript)
javascriptfunction f(m, n) { if (m * n == 0) { return m + n + 1 } return f(m - 1, f(m , n - 1)) } console.log(f(2, 1)) // 5
摘自电子书ECMA6 入门中的 尾递归 的定义:
函数调用自身,称为递归。如果尾调用自身,就称为尾递归。
引子代码中的函数f是return了自身,但是其第二个参数又调用f,那么在这种情况下,
f算不算是尾递归呢?f不是尾递归,又如何改成尾递归(如能改)?Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
不是尾递归。。
f(m , n - 1)执行结束后需要向上层返回执行结果,也就是把结果给f(m - 1, f(m, n - 1))然后继续递归。。那么程序运行时必然会保存f函数上一层的状态,所以这跟普通递归一样的题目里面的不是尾递归,因为函数的最后实际相当于如下形式,很显然不是尾递归。
而把这个函数改造成尾递归是可行的,实际上任何函数都可以改造成尾递归形式。
不过可惜的是,javascript 不支持尾递归优化,改成这种形式之后反而因为增加了中间层次导致挂的更快,所以这个变换在 javascript 里面也只有理论意义而已。
當且僅當尾調用自身。
return f(m - 1, f(m , n - 1))中的f(m , n - 1)顯然不是尾調用。