算法中的递归和尾递归

程序员文章站 2024-02-11 23:37:40

...

1 递归

1.1 什么是递归

递归：在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。也就是说，递归算法是一种直接或者间接调用自身函数或者方法的算法。

通俗来说，递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。

1.2 递归的基本原理

递归的基本步骤：

每一级的函数调用都有自己的变量。
每一次函数调用都会有一次返回。
递归函数中，位于递归调用前的语句和各级被调用函数具有相同的执行顺序。
递归函数中，位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反
虽然每一级递归都有自己的变量，但是函数代码并不会得到复制。

1.3 递归的优缺点

1.3.1 优点

实现简单
可读性好

1.3.2 缺点

递归调用，占用空间大
递归太深，容易发生栈溢出
可能存在重复计算

1.4 递归的三大要素

第一要素：明确你这个函数想要干什么。先不管函数里面的代码什么，而是要先明白，你这个函数的功能是什么，要完成什么样的一件事。
第二要素：寻找递归结束条件。需要找出当参数为啥时，递归结束，之后直接把结果返回，请注意，这个时候必须能根据这个参数的值，能够直接知道函数的结果是什么。
第三要素：找出函数的等价关系式。还要不断缩小参数的范围，缩小之后，可以通过一些辅助的变量或者操作，使原函数的结果不变。

1.5 递归的过程

算法中的递归和尾递归
具体地说，如果递归函数调用自己，则被调用的函数也将调用自己，这将无限循环下去，除非代码中包含终止调用链的内容。通常的方法将递归调用放在if语句中。例如，void类型的递归函数recursive()的代码如下：

void recursive(argumentlist){
	statements1;
	if(test){
		recursive(argumens);
	}
	statements2;
}

用文字再现这段代码块的内容：
只要if语句为true，每个recursive()调用都将执行statements1，然后再调用recursive()，而不会执行statements2。当前调用结束后，程序控制权将返回给调用它的recursive()，而该recursive()将执行其statements2部分，然后结束，并将控制权返回给前一个调用，依次类推。

1.6 递归的使用

递归的强大之处在于它允许用户用有限的语句描述无限的对象。因此，在计算机科学中，递归可以被用来描述无限步的运算，尽管描述运算的程序是有限的。这一点是循环不太容易做到的。
编写正确的递归算法，一定要有归 的步骤，也就是说递归算法，在分解问题到不能再分解的步骤时，要让递归有退出的条件，否则就会陷入死循环，最终导致内存不足引发栈溢出异常。

递归求阶乘

int jie (int n ){
        if (n ==1||n==0){//终止条件
            return 1;
        }else {
            int sum;
            sum = n*jie(n-1);//相同重复逻辑
            return sum;

1.7 递归优化

递归问题中想到思路本身不非常难，真正的难点在于如何优化

1.7.1 考虑是否重复计算

如果使用递归的时候不进行优化，是有非常非常非常多的子问题被重复计算的。因此，使用递归的时候，必要须要考虑有没有重复计算，如果重复计算了，一定要把计算过的状态保存起来。

1.7.2 考虑尾递归

对于递归的问题，一般都是从上往下递归的，直到递归到最底，再一层一层着把值返回。

int recursive(int n,int res){
	if(n <0){
		return 0;
	}else if(n==0){
		return 1;
	}else if(n==1){
		return res;
	}else{
		return recursive(n-1,n*res);
	}
}

不过，有时候当n比较大的时候，例如当n = 10000时，那么必须要往下递归10000层直到 n <=1 才将结果慢慢返回，如果n太大的话，可能栈空间会不够用。这个时候，就可以用尾递归优化来解决。

转载于：https://baijiahao.baidu.com/s?id=1629571574350179349&wfr=spider&for=pc

2 尾递归

2.1 一般递归和尾递归区别

2.1.1 再熟悉一般递归

一般递归：

def normal_recursion(n):
    if n == 1:
        return 1
    else:
        return n + normal_recursion(n-1)

执行的压栈情况如下：

normal_recursion(5)
5 + normal_recursion(4)
5 + 4 + normal_recursion(3)
5 + 4 + 3 + normal_recursion(2)
5 + 4 + 3 + 2 + normal_recursion(1)
5 + 4 + 3 + 3
5 + 4 + 6
5 + 10
15

可以看到, 一般递归, 每一级递归都需要调用函数, 会创建新的栈，随着递归深度的增加, 创建的栈越来越多, 造成爆栈:boom:

2.1.2 了解尾递归

尾递归基于函数的尾调用，每一级调用直接返回函数的返回值更新调用栈,而不用创建新的调用栈, 类似迭代的实现, 时间和空间上均优化了一般递归

def tail_recursion(n, total=0):
    if n == 0:
        return total
    else:
        return tail_recursion(n-1, total+n)

执行压栈情况：

tail_recursion(5)
tail_recursion(4, 5)
tail_recursion(3, 9)
tail_recursion(2, 12)
tail_recursion(1, 14)
tail_recursion(0, 15)
15

可以看到, 每一级递归的函数调用变成线性的形式.

2.2 深入理解尾递归

2.2.1 尾递归原理

当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。

2.2.2 尾递归特点

尾递归在普通尾调用的基础上，多出了2个特征：

在尾部调用的是函数自身（Self-called）；
可通过优化，使得计算仅占用常量栈空间 (Stack Space)。

2.2.3 尾递归说明

传统模式的编译器对于尾调用的处理方式就像处理其他普通函数调用一样，总会在调用时创建一个新的栈帧（stack frame）并将其推入调用栈顶部，用于表示该次函数调用。

当一个函数调用发生时，电脑必须 记住 调用函数的位置 —— 返回位置，才可以在调用结束时带着返回值回到该位置，返回位置一般存在调用栈上。在尾调用这种特殊情形中，电脑理论上可以不需要记住尾调用的位置而从被调用的函数直接带着返回值返回调用函数的返回位置（相当于直接连续返回两次）。
尾调用消除即是在不改变当前调用栈（也不添加新的返回位置）的情况下跳到新函数的一种优化（完全不改变调用栈是不可能的，还是需要校正调用栈上形式参数与局部变量的信息）

由于当前函数帧上包含局部变量等等大部分的东西都不需要了，当前的函数帧经过适当的更动以后可以直接当作被尾调用的函数的帧使用，然后程序即可以跳到被尾调用的函数。产生这种函数帧更动代码与 jump（而不是一般常规函数调用的代码）的过程称作尾调用消除(Tail Call Elimination)或尾调用优化(Tail Call Optimization, TCO)。尾调用优化让位于尾位置的函数调用跟 goto 语句性能一样高，也因此使得高效的结构编程成为现实。

然而，对于 C++ 等语言来说，在函数最后 return g(x); 并不一定是尾递归——在返回之前很可能涉及到对象的析构函数，使得 g(x) 不是最后执行的那个。这可以通过返回值优化来解决。

在尾递归中，首先执行计算，然后执行递归调用，将当前步骤的结果传递给下一个递归步骤。这导致最后一个语句采用的形式(return (recursive-function params))。基本上，任何给定递归步骤的返回值与下一个递归调用的返回值相同。
我们考虑一个最基本的关于N的求和函数，（例如sum(5) = 1 + 2 + 3 + 4 + 5 = 15）。
这是一个使用JavaScript实现的递归函数：

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

如果你调用recsum(5)，JavaScript解释器将会按照下面的次序来计算：

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

注意在JavaScript解释器计算recsum（5）之前，每个递归调用必须全部完成。
这是同一函数的尾递归版本：

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

下面是当你调用tailrecsum(5)的时候实际的事件调用顺序：

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

在尾递归的情况下，每次递归调用的时候，running_total都会更新。