尾递归

发布时间 2023-06-06 17:34:14作者: yuluoxingkong

递归,我们大家都会吧,但是有一种叫做尾递归的,了解吗?本文主要讲解一下尾递归的事儿。

一、引入

编程题:输入一个整数n,输出斐波那契数列的第n项

 给你来个简单点儿的例子,计算n的阶乘

二、递归实现

function fibonacci(n) {
  if (n === 0 || n === 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

 三、普通递归的问题:

上面的递归实现,是确实能解决问题的,毫无疑问!但是,当我们在测试的时候,用一个较大的数字,百日fibonacci(50)fibonacci(100)...,你会发现运行要等待很久。如果数字再大一点,还会出现堆栈异常,为什么会很慢,堆栈异常呢。关于原理,请参考

张大胖学递归一文。此文详细讲解了递归对栈的使用原理。简单来说,就是数字太多,递归的栈存储空间会很大,大量的入栈,出栈,等等会消耗很多时间。同时栈不可能无限大。当n较大到超过栈空间的容量大小,就会产生异常

四、什么是尾递归