人生的烦恼,多在于知道的太多,而做的太少。

递归和尾递归

算法 zhangman523@gmail.com 1292℃ 0评论

递归原理

递归是一种解决问题的有效方法,在递归过程中,函数将自身作为子例程调用

你可能想知道如何实现调用自身的函数。诀窍在于,每当递归函数调用自身时,它都会将给定的问题拆解为子问题。递归调用继续进行,直到到子问题无需进一步递归就可以解决的地步。

为了确保递归函数不会导致无限循环,它应具有以下属性:

  • 一个简单的基本案例(basic case)(或一些案例) —— 能够不使用递归来产生答案的终止方案。
  • 一组规则,也称作递推关系(recurrence relation),可将所有其他情况拆分到基本案例。

注意,函数可能会有多个位置进行自我调用。

尾递归

尾递归函数是递归函数的一种,其中递归调用是递归函数中的最后一条指令。并且在函数中应该只有一次递归调用。

尾递归的好处是,它可以避免递归调用期间栈空间开销的累积,因为系统可以为每个递归调用重用栈中的固定空间。

我们来看下面的例子:

请注意,在尾递归的情况下,一旦从递归调用返回,我们也会立即返回,因此我们可以跳过整个递归调用返回链,直接返回到原始调用方。这意味着我们根本不需要所有递归调用的调用栈,这为我们节省了空间。

尾递归函数可以作为非尾递归函数来执行,也就是说,带有调用栈并不会对结果造成影响。通常,编译器会识别尾递归模式,并优化其执行。然而,并不是所有的编程语言都支持这种优化,比如 CC++ 支持尾递归函数的优化。另一方面,JavaPython 不支持尾递归优化。

转载请注明:zhangman523 » 递归和尾递归

喜欢 (4)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址