递归算法

2020-12-04 本文已影响0人清风烈酒2157

[toc]

递归

一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的

首先你要理解函数调用的本质:

保存当前指令地址
跳转到被调用函数(指令段)的起始地址实际过程比这个复杂, 比如还包括保存临时变量和传参等等, 但是对我们正在讨论的问题不起到本质影响所以省略掉不谈
函数调用并不是在原地展开代码
每一个函数都是一段独立存在于存储器中的指令序列
每个程序的内存空间中都包括一个叫做"栈(stack)"的区域, 它的特点是先进后出, 就像一摞书, 只能往顶端放书, 也只能从顶端取书每当你调用一次函数, 就会向栈中压入(push)返回地址, 当函数返回(return)时从栈中弹出(pop)返回地址并跳转回返回地址.
所以, 自身调用乃至循环调用形成的递归调用在进行时, 就会不断压栈来保存函数运行状态, 当递归一层一层返回时, 则是不断出栈了函数调用并不是在原地展开代码

单次调用递归

示例一

函数:
void func(int N){
    N++;
    if (N>2){
        return;
    }else{
        printf("%d\n",N);
        func(N);

    }
}
调用:
func(0);

打印

1
2

分析 :

N=1,先打印1,入栈.
N=2,先打印2,入栈.
N=3,开始出栈.
函数执行完毕

栈有几个这里会走几次,表示正在出栈

4e1859f1fc53386049ad2821fbf9130d

示例二

void func(int N){
    N++;
    if (N>2){
        return;
    }else{
        func(N);
        printf("%d\n",N);
    }
}

打印

2
1

分析:

N=1,入栈
N=2,入栈
N=3,不入栈,直接出栈
栈顶,N=2,要出栈,但是并没有出栈,而是执行下面的打印,打印完后出栈,N=2也出栈
栈顶,N=1,要出栈,但是并没有出栈,而是继续执行打印,打印完出栈,N=1出栈,函数执行完毕.
示例三

void func(int N){
    N++;
    if (N>2){
        return;
    }else{
        func(N);
    }
    
     printf("%d\n",N);
}

打印

2
1

分析,和示例二一样

两次调用递归

示例一

void func(int N){
    N++;
    if (N>2){
        return;
    }else{
        printf("%d\n",N);
        func(N);
        func(N);
    }
    
}

打印

1
2
2

分析

N=1,N=2,入栈之前都会先打印1,2
N=3,不满足递归条件,跳出
N=2,要出栈,但是不是先出栈而是走下面的函数func(N);
但是N=2,又是得到N++=3,出栈,然后N=2也出栈,
N=1,要出栈,也是先走下面func(N),
N=1,N++=2 ,入栈,先打印2
然后N=2,上下函数都是N=3,出栈,然后N=1出栈,函数执行完毕

示例二

void func(int N){
    N++;
    if (N>2){
        return;
    }else{
        func(N);
        printf("%d\n",N);
        func(N);
    }
    
}

打印

2
1
2

分析

N=1,N=2,入栈
N=3,不满足出栈,跳出
栈顶N=2,出栈,但是并没有先出栈,先打印2,并执行下面函数func(N),得到N=3,不满足,直接出栈.
N=2出栈然后出栈.
接着N=1开始出栈,继续先打印,在执行函数func(N).
函数执行得到N++2,满足入栈,然后调上面 func(N),不满足入栈直接出栈,继续调用打印,然后,调用下面 func(N),不满足直接出栈,
N=1出栈.函数执行完毕.

最后这个执行两次分别是下面函数N=2时不满足出栈,和之前要出栈有执行打印和函数的那个N=1出栈.

160bc11cf1b39933297afdacc25fd5ea

示例三

void func(int N){
    N++;
    if (N>2){
        return;
    }else{
        func(N);
        func(N);
        printf("%d\n",N);
    }
}

打印


2
2
1

分析
N=1,N=2,依次入栈.
N=3,不满足入栈条件,跳出;
当N=2要出栈,但是没有先出栈,先执行func(N);,
得到N++=3,不满足直接跳出,然后执行打印;
然后N=2出栈,得到N=1;
执行下面函数func(N).
执行上面函数得到N=2,又调到下面函数,下面函数执行到N=3跳出,直接打印,打印执行完出栈,N=1出栈,最后打印1;

出栈,后面有函数,会先执行,执行完才出栈,

参考

原来连续两次递归调用很简单

递归算法

递归

首先你要理解函数调用的本质:

单次调用递归

两次调用递归

参考

猜你喜欢

热点阅读