理解一种特殊的递归算法
理解一种特殊的递归算法
提问于 2021-09-15 11:23:33
下面的算法Delta解决了哪一个问题，其中m，n >= 0是整数？
因此，我发现由于嵌套递归的性质以及它如何调用另一个递归算法，该算法很难分解。如果我不得不猜测，我会说达美解决了LCS(最长公共子序列)问题，但我无法给出一个很好的解释为什么。
有人能帮我分解算法，解释递归以及它是如何工作的吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2021-09-15 14:16:52
正如您自己发现的，增量计算两个整数的乘积。
递归确实令人费解，但获得直觉的最佳方法是手动对一些示例数据执行计算。但是，通过单独查看这些函数，您会发现：
伽玛只是求和。Gamma(n,m) = gamma(n, m - 1) + 1本质上执行一个简单的求和，在第二个项中进行计数，同时在第一个项中添加1。示例：
3+3=
(3 + 2) +1=
(3+ 1) +1=
((3+ 0) + 1) +1=
6
知道了这一点，我们可以简化Delta：
Delta(n, m) = n + Delta(n, m - 1) (如果m!=0，否则返回)。
同样地，我们计算的是第二个因子，但不是加1，而是加n。这确实是乘法的一个定义。如果您像上面这样手动地解决一个例子，这是很容易理解的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/69192181
复制相关文章
相似问题
腾讯云开发者
