• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

我对递归的理解和总结

开发技术 开发技术 1个月前 (01-30) 14次浏览

看了自己的动态记录,发现自己已经遗忘了曾经的自己,有一条动态,2013年的时候,我看了一篇关于尾递归的博文,那时候还只是一个初学者,胡乱评论了一下,作者希望我能写一篇博文发表一下自己的看法,现在作者应该早就搞清楚了这些,但还是写一下,画个句号吧。不保证说的没问题,只希望如果有像我当年一样的初学者看到,可以参考借鉴,或许能有些帮助。

 

1. 递归就是一个函数直接或间接的自己调用自己,间接就是f0 -> f1 -> f0 ->f1这种,但也就是一个名词而已,并不神奇,它只是一个普普通通的函数调用,但由于自己调用自己这个特性,有一种自动化的力量,给它一个规则,它可以自动的持续运行下去,直到触发停止条件。一个递归函数就像是一个简单的计算机。

2. 所有的递归都可以用循环来替代,所有的循环也都可以用递归来替代,两者是等价的。

3. 递归是人脑的直接思维方式,循环是当前多数(我所知道的所有的)cpu的直接思维方式。

4. 对于cpu来讲,函数调用只是寄存器,内存,跳转等操作,如果不涉及额外栈空间使用(极简单函数的特殊情况),函数调用和循环的差别可能仅仅是使用的寄存器不同。

5. 递归可以把复杂的问题变得简单,是一种处理问题的模型。比如汉诺塔,快速排序,二叉树遍历查找,如果学会使用递归这种思维方式思考问题,很多问题会变得很简单,大事化小,小事化了,每一步都是很简单的操作。

6. 正确的思维会使问题很简单,错误的思维会让人发懵,使用递归的思考方式是忘记调用的是自己,自己调用的是任意一个函数,那个函数有没有实现,是否实现得正确不是我现在要关心的事,我只要保证,在那个函数正确实现的前提下,我现在写的这个函数是没问题的,当我写完当前函数的时候,被调用的函数也就写完了(副产物),因为它们是同一个,这有点像数学归纳法。

7. 正确的实现一个递归函数,需要保证有退出的条件,除非你是在写一个死循环,同时随着递归层数变深,问题逐渐简单化,规模逐渐缩小,或者是向退出条件逼近(收敛)。

8. 递归对栈空间的占用分两种,尾递归开启相应的优化之后不会导致栈空间使用不停扩大,非尾递归对栈空间的调用要看递归的层数,递归层数是可预测的,一般二分的递归(理想的情况,极端的情况二叉树会变成链表,这时候已经不是二分法了,但二叉树是可以事先保证平衡的)层数大约为log2(n),30层函数调用使用的栈空间很少(使用超级庞大的数组局部变量这样的特殊情况除外),但是n是10亿级别,这个时候要关注的已经不是栈空间了,而是保存数据的内存空间或cpu等资源,比如用递归方法计算Fibonacci数列,现在的个人电脑默认栈空间(M级别),不可能栈溢出的,忙不过来的是cpu,多分的情况栈空间一般都不会过深,原因是一边调用增加深度,一边返回减少深度,用完全平衡二叉树为例,画一个图看一下调用过程就一目了然。

 

下面就栈空间的使用,尾递归,递归循环的转换等问题详细分析。

除非是特殊的情况,编译器能优化成不使用栈空间,否则递归是需要栈空间的,这和任何一个函数调用都是一样的,对于解决实际问题的函数,一般没有不需要栈空间的,在函数调用的时候,需要保存cpu寄存器到栈空间(用于恢复函数的执行),局部变量也有可能会导致栈空间的使用,每一个函数执行的时候局部变量都会占用一次栈空间,每一次函数调用也会触发一次栈空间的使用,这就是每一次递归调用的栈空间代价,函数调用总是有调用就有返回的,最大代价就是最大递归层数,尾递归是一种特殊情况,考虑下面的函数。

int f(int n)
{
    if(n <= 0)
       return n;
    // body;
    return f(n-1);
}
return f(n-1);是函数f的最后一个语句。f(n-1)的返回值就是f(n)的返回值,也就是说对于当前函数f(n)已经没有必要保存现场了,它的栈空间不需要恢复了,f(n-1)返回到f(n),f(n)再向上返回,那为什么要留个中介呢,为什么不直接向上返回呢,所以栈空间中保存的返回地址等不动,进入f(n)时保存的寄存器(callee-saved registers)不动,也就是f(n)的上层现场不动,他们直接继承给f(n-1),f(n-1)不再
保存它的返回地址(f(n)的最后),也不再保存使用的寄存器(f(n)已经不需要恢复了),f(n)的局部变量使用的栈空间直接被f(n-1)的给覆盖掉,同样的逻辑再向上递推,会发现,每一层函数调用引起的栈空间占用都相当于没有了,实际上上述代码就变成了
int f(int n)
{
    while( n > 0 )
    {
        //body;
        n--;
    }
    return n;
}

这种递归叫做尾递归,即递归调用之后不需要再有额外的操作,并且递归之前没有其他递归调用,开启优化之后(gcc, O2默认开启)编译器可以将尾递归优化成循环。

再考虑下面的函数

int f(int n)
{
    if(n <= 0)
       return n;
    // body;
    return n + f(n-1);
}

这种递归调用是无法 直接 变成循环的,这里用直接,是因为这种情况太简单了,编译器不会那么傻,gcc O1就会变成循环,为什么不能直接变成循环呢,因为f(n-1)之后还有其他操作(返回值+n),为了继续其他操作能够继续执行,调用f(n-1)之前需要保存现场,需要用到栈空间,每一层调用都会保存一次栈空间,这时候栈空间的占用是O(n)的,因为不是二分,三分,n的数量稍大一点就会导致栈溢出。当然这里实在是太简单了!换个复杂的,编译器就不会优化了(只是写本文的时候用的gcc,不排除以后编译器越来越智能的可能)。

unsigned long fib(int n)
{
    if(n < 2)
       return 1;
    return fib(n-1) + fib(n-2);
}

fib(3) 调用 fib(2)和fib(1),假定编译器生成的指令是先调用fib(2),那么就要在栈空间中保存现场,以便fib(2)返回的时候能够继续执行fib(1)和一个加法操作,fib(2)调用fib(1)和fib(0),还是假定先调用左边的,调用fib(1)的时候需要保存现场,然后返回1, 恢复现场,保存现场,调用fib(0),然后恢复现场,加法运算,然后再返回上层,即fib(2)返回,恢复现场,fib(2)下面的所有调用占用的栈空间都已释放了(递减栈栈顶寄存器数值增加),然后保存现场,调用fib(1),返回1, 恢复现场,加法运算,返回,整个fib(3)就是这样完成的,可见每次调用+左边的分支的时候,递归层数会增加一层,每次调用+右面的分支的时候,左面增加的层数都已经恢复,这是一个动态增减的过程,递归层数是有限的。这种Fibonacci数列算法慢的根源在于重复计算。不重复计算的方法如下:

unsigned long fib2(int n,  unsigned long left, unsigned long right)
{
    if( n < 2 )
        return right;
    return fib2(n - 1, right, left+right);
}

这里是一个尾递归,相当于循环, 当然如果不优化,栈空间占用是O(n),n足够大是会溢出的。

可见,循环和尾递归是直接互相转换的,循环变量相当于函数中的参数,循环退出条件相当于函数退出的条件,循环变量的增减相当于参数传递时的增减计算,循环体相当于函数体,所以像scheme这样的编程语言没有循环但是并不影响表达能力。

Fibonacci数列循环的算法是从数列的左边开始,不符合直观定义,需要知道原理才能想到,直观的定义是从右到左,然而左边又没有准备好,所以需要借用栈。

考虑一个更明显的例子,单向非循环链表的正向遍历和逆向遍历,前者是尾递归(循环),后者非尾递归(使用循环需要借助栈),正向遍历不需要额外的栈空间,但是如何实现逆向遍历呢?首先要拿到最后一个节点,但是访问完最后一个节点了,到哪里去找上一个节点呢,单向链表并没有prev指针,很明显,需要在内存中保存,由于访问的顺序是后进先出,用的应该是栈这种模型,而函数调用本来就是栈的模型的,所以如果使用函数调用的方式是很自然的,很符合人的思维逻辑的,用递归的方式都不用考虑栈的问题,因为这是一种很自然的符合人的逻辑的思考模型,代码如下:

struct list{
    int c;
    struct list *next;
};

#define print_list(list) (void)list
void visit(const struct list *cur)
{
    if(cur == NULL)
        return;
    print_list(cur);
    visit(cur->next);
}
void visit_reverse(const struct list *cur)
{
    if(cur == NULL)
        return;
    // 访问后面的,怎么访问的不用管,会有人保证它的逆序
    visit_reverse(cur->next);
    // 后面的全都访问完了,访问当前的
    print_list(cur);
}

#define list_append(tail_p, cur) ((*tail_p)->next = cur, (*tail_p) = cur)
struct list * _list_reverse(struct list *cur, struct list **tail_after_reverse)
{
    // 最后一个
    if(cur->next == NULL)
    {
        // 记录末尾,方便list_append
        *tail_after_reverse = cur;
        return cur;
    }
    struct list *head = _list_reverse(cur->next, tail_after_reverse);
    list_append(tail_after_reverse, cur);
    return head;
}
// 逆序单向链表
struct list * list_reverse(struct list *cur)
{
    struct list *tail_after_reverse;
    if(cur == NULL)
        return cur;
    struct list *head = _list_reverse(cur, &tail_after_reverse);
    list_append(&tail_after_reverse, NULL);
    return head;
}

 

尾递归和循环可以互相转换,这是很明显的,那么非尾递归如何和循环互相转换呢,理论上是一定可以完成的,因为对于cpu来讲递归就是用栈来实现的,下面以二叉树的先序,中序,后序的遍历方式来举例说明,不过能够实现不代表应该这样做,代码的可读性和见解性非常重要,并且转变成循环也未必就能感受到性能的变化。

#include <assert.h>
#include <stdio.h>


struct tree{
    int n;
    struct tree *left;
    struct tree *right;
};

static const void *stack[128];
static char stack_flag[128];
static int stack_i;
#define visit(t) printf("%dt", t->n)
#define push(x) do{if(x) stack[stack_i++] = x;}while(0)
#define pop() (stack_i == 0 ? NULL : stack[--stack_i])
#define push2(x, flag) do{if(x) {stack[stack_i] = x; stack_flag[stack_i++] = flag;}}while(0)
#define pop2(flag) (stack_i == 0 ? NULL : ((flag=stack_flag[--stack_i]), (stack_flag[stack_i] = 0), stack[stack_i]))

// 二叉树的先序遍历
//
// 递归版本
void preorder(const struct tree *t){
    if(t == NULL)
        return;
    visit(t);
    preorder(t->left);
    preorder(t->right);
}

// 循环版本
// 如何变成循环呢,方法就是递归怎么来,我们就怎么来,
// 1. 调用visit,但是调用之后要恢复两个函数调用,为了恢复现场,需要在栈空间中保存后续要做的事,我们这里显然不需要保存cpu寄存器等,只需要保存t->left和t->right就可以了,由于是先调用t->left,后调用t->right,所以入栈就要反过来。
//push(t->right);
//push(t->left);
//能不能直接push(t)呢,答案是不能,除非标记t已经访问过了,否则就循环访问t了,但是标记t访问过了还是要把t->right和t->left入栈,不如就直接来,更直接。
// 2. t访问完了,递归程序就恢复现场,返回到visit的下一个地址执行,恢复现场就对应我们的出栈,继续执行同样的preorder逻辑就相当于我们重复一次循环,
// 3. 递归程序继续这个过程,直到函数栈上的最底层,也就是最后一个函数调用返回,对应我们的继续这个过程,直到栈里面没有数据了为止。
// 代码如下
void preorder_loop0(const struct tree *in)
{
    const struct tree *t = in;
    if(t == NULL)
        return;
    do{
        visit(t);
        push(t->right);
        push(t->left);
    }while((t = pop()) != NULL);
}
//这个程序是最原始的贴近递归的版本,还可以继续优化,visit(t)之后pop出来的一定是t->left,那么下次一定是visit(t->left),往下递推,每一次都是visit(t->left),也就是说按照一直向左的方向遍历就可以了,需要入栈的只是右子树,但是右子树谁先谁后呢,从递归程序可以看出,所有的左子树成员都在右子树的前面遍历,也就是说最接近树根的大叉是优先级最低的,远离树根的在左子树上的右子树更优先,也就是说,入栈的顺序和访问的顺序相同,即
//

void preorder_loop1(const struct tree *in)
{
    const struct tree *t = in;
    if(t == NULL)
        return;
    do{
        while(t)
        {
            visit(t);
            push(t->right);
            t = t->left;
        }
    }while((t = pop()) != NULL);
}
// 将上面两种版本对比,想象一下preorder_loop0的执行过程,也可以直接优化为preorder_loop1

//中序遍历
// 递归版本
void inorder(const struct tree *t){
    if(t == NULL)
        return;
    inorder(t->left);
    visit(t);
    inorder(t->right);
}

// 第一步还是按照和递归一一对应的方式来转换成循环,这个地方有点复杂,因为第一个函数不是visit,本身就是个递归的,这时候的处理方式不唯一,可以直接把递归版本函数中最上面的那个inorder展开,也可以按照通用的循环中的逻辑来处理那个inorder,前者直接就是优化之后的了。另外由于inorder和visit是两种操作,为了区分是哪一种操作,还需要在入栈的时候加标记等。
void inorder_loop0(const struct tree *in)
{
    int is_visit = 0;
    const struct tree *t = in;
    if(t == NULL)
        return;
    do{
        if(is_visit)
            visit(t);
        else
        {
            push2(t->right, 0);
            push2(t, 1);
            push2(t->left, 0);
        }
    }while((t = pop2(is_visit)) != NULL);
}
// 简化push(t->left); 同preorder的方法
void inorder_loop1(const struct tree *in)
{
    int is_visit = 0;
    const struct tree *t = in;
    if(t == NULL)
        return;
    do{
        if(is_visit)
            visit(t);
        else
        {
            while(t)
            {
                push2(t->right, 0);
                push2(t, 1);
                t = t->left;
            }
        }
    }while((t = pop2(is_visit)) != NULL);
}
// 继续优化,每次pop出来的一定是先visit的,然后接着就是它的right,那么两者可以合成一个整体,这样也不用标记是否是is_visit了
void inorder_loop2(const struct tree *in)
{
    const struct tree *t = in;
    if(t == NULL)
        return;

    while(t)
    {
        push(t);
        t = t->left;
    }
    while((t = pop()) != NULL)
    {
        visit(t); // pop -> t
        if(t->right) // pop -> t->right
        {
            t = t->right;
            while(t)
            {
                push(t);
                t = t->left;
            }
        }
    }
}

// 后续遍历
// 递归版本
void postorder(const struct tree *t){
    if(t == NULL)
        return;
    postorder(t->left);
    postorder(t->right);
    visit(t);
}
// 和中序遍历相同的方式,唯一一个区别就是 visit(t) 和postorder(t->right)的顺序换了一下,也就是入栈的顺序换了一下。代码如下:
void postorder_loop0(const struct tree *in)
{
    int is_visit = 0;
    const struct tree *t = in;
    if(t == NULL)
        return;
    do{
        if(is_visit)
            visit(t);
        else
        {
            push2(t, 1);
            push2(t->right, 0);
            push2(t->left, 0);
        }
    }while((t = pop2(is_visit)) != NULL);
}

// 前面已经用过这种思路,去掉push t->left(附带的pop也一起去掉了)
void postorder_loop1(const struct tree *in)
{
    int is_visit = 0;
    const struct tree *t = in;
    if(t == NULL)
        return;
    do{
        if(is_visit)
            visit(t);
        else
        {
            while(t)
            {
                push2(t, 1);
                push2(t->right, 0);
                t = t->left;
            }
        }
    }while((t = pop2(is_visit)) != NULL);
}

// t->right 先出栈,处理完整棵树才能继续处理t(即visit(t)),所以t和t->right不能当成一个整体来优化
// 但仍然可以继续优化,t->right的处理过程是先push 它自己,也就是说visit(t)的时候上一次pop一定是
// t->right,并且pop -> t->right 然后pop -> t 的时候一定是访问t的时候,这是后序遍历的定义的必然
// 即 t->right == NULL 或last_pop/visit == t->right就是visit(t)的时刻,这样可以去掉is_visit的标记
// 使用更简单的push 和 pop
void postorder_loop2(const struct tree *in)
{
    const struct tree *t = in, *last_visit = NULL;
    if(t == NULL)
        return;

    while(t)
    {
        push(t);
        push(t->right);
        t = t->left;
    }
    while((t = pop()) != NULL)
    {
        if(t->right == NULL || last_visit == t->right)
        {
            visit(t);
            last_visit = t;
        }
        else
        {
            while(t)
            {
                push(t);
                push(t->right);
                t = t->left;
            }
        }
    }
}

int main(int argc, char *argv[])
{
    /*
     *
     *                        4
     *                     /    
     *                   2        6
     *                 /        /   
     *                1    3    5      8
     *                                / 
     *                               7   9
     *
     *
     */
    struct tree t[9] = {
        {1, NULL,NULL},
        {2, &t[0],&t[2]},
        {3, NULL,NULL},
        {4, &t[1],&t[5]},
        {5, NULL,NULL},
        {6, &t[4],&t[7]},
        {7, NULL,NULL},
        {8, &t[6],&t[8]},
        {9, NULL,NULL},
    };
    preorder(&t[3]);
    puts("");
    assert(stack_i == 0);
    preorder_loop0(&t[3]);
    assert(stack_i == 0);
    puts("");
    preorder_loop1(&t[3]);
    assert(stack_i == 0);
    puts("");
    inorder(&t[3]);
    assert(stack_i == 0);
    puts("");
    inorder_loop0(&t[3]);
    assert(stack_i == 0);
    puts("");
    inorder_loop1(&t[3]);
    assert(stack_i == 0);
    puts("");
    inorder_loop2(&t[3]);
    puts("");
    postorder(&t[3]);
    puts("");
    assert(stack_i == 0);
    postorder_loop0(&t[3]);
    assert(stack_i == 0);
    puts("");
    postorder_loop1(&t[3]);
    assert(stack_i == 0);
    puts("");
    postorder_loop2(&t[3]);
    assert(stack_i == 0);
    return 0;
}

尾递归和非尾递归是否能转换呢,对于Fibonacci数列这样的特殊情况当然可以,但有些问题就是递归模型,比如快速排序,所以是无法直接转换的,如果非要转换的话,也是可以的,借助额外实现的栈,因为循环和尾递归是等价的,循环加额外的栈能实现的,尾递归加额外的栈也能实现,但是这样做是否有意义呢,人工精心优化的循环/尾递归程序和非尾递归相比,有时候也许能获得少量性能提升,但是代码的可读性却很差,而非尾递归程序却是非常直观。

补充一点,看编译器是否进行了尾递归优化,可以通过gdb或objdump看汇编,看尾递归发生的时候后面是否有其他操作,或者是否还有递归的调用,gcc O2一定会优化的, 如果通过试验测试,建议数字要足够大,因为优化之后的程序可能占用栈空间很小,而进程的栈空间可能又很大,所以没有进行尾递归优化依然可能不会栈溢出。

 

总之,递归是一种非常好的模型,栈空间一般可预测,尾递归因为利用函数实现,局部变量隔离,也会增加安全性,但是记得开优化,尽量不用栈和循环替代递归,增加代码可读性。


程序员灯塔
转载请注明原文链接:我对递归的理解和总结
喜欢 (0)