递归

42oUGHeDo · 2023-08-30 11:37:48 · 个人记录

先将明白一点四点

•递归是一种思想。

•递归是一种思维方式。

•递归是一种算法。

•一个函数直接或间接调用自己——递归函数

递归是个神马东西？

~~OS:它不是个东西~~

• 原始问题可转化为：解决方法相同的新问题，新问题的规模比原始问题小

• 新问题又可转化为解决方法相同的规模更小的新问题。

• 上述过程不能无限进行。

• 这种解决问题的方法是递归方法。

好像没用……（其实就是没用）

程序设计中的递归方法

• 通过函数调用自己本身，实现将问题转化为本质相同，但规模较小的子问题的方法。

• 如果是直接调用自身，称为直接递归；如果是通过其它函数间接调用自身，则称为间接调用。

~~我自己都不明白~~

直接递归长成这个样子ヾ(❀^ω^)ノﾞ

int abc()
{
    ……
    abc ()
    ……
}

直接递归长成这个样子^(*￣(oo)￣)^

int abc ()
{
    ……
    xyz()
    ……
}

int xyz()
{
    ……
    abc()
    ……
}

上点栗子

(・◇・)？数楼梯(⊙_⊙)?

~~这题高精，so直接用下面的代码是过不了的~~--O(∩∩)O哎嘿~_

• 一个含有n阶的楼梯，一次可以走1阶或2阶，从底走到顶一共有多少种走法？

• 输入：台阶数n

• 输出：不同走法种数

• 输入样例：3

• 输出样例：3

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<string>
#include<cmath>
#include<stack>
#include<deque>
#include<map>
//#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int a=1,b=2,c;
int main() 
{
    //freopen("fruit.in","r",stdin);
    //freopen("fruit.out","w",stdout);
    ios::sync_with_stdio(false);
    while (cin>>n)
    {
        if (n==0)
        {
            cout<<0<<endl;
            return 0;
        }
        if (n<3)
        {
            if (n==1)
            {
                cout<<1<<endl;
                return 0;
            }
            else
            {
                cout<<2<<endl;
                return 0;
            }
        }
        for (int i=3;i<=n;i++)
        {
            c=a+b;
            a=b;
            b=c;
        }
        cout<<c<<endl;
        a=1;b=2;
    }

    return 0;
}

我把代码放前面了……

┏┛墓┗┓...(((m-__-)m…………

~~思路应该有人看吧~~

先找递归式

1阶楼梯时

只有1种可能——1步直接上去；

2阶楼梯时

有2种可能——1步走两次，或2步走一次上去；

3阶楼梯时

有3种可能——每次都走1级，第1次走1级，第2次走2级；第1次走2级，第2次走1级；

可以得出一个递归式：a[i]=a[i-1]+a[i-2];

(这里i保证大于3，i相当于c，i-1相当于b，i-2相当于a）

~~长得挺像递推的~~(＾－＾)V

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<string>
#include<cmath>
#include<stack>
#include<deque>
#include<map>
//#include<bits/stdc++.h>
#define ll long long
using namespace std;
int step (int n) {
    if (n==1 || n==2)
        return n;
    return step(n-1)+step(n-2);
}
int main() {
    //freopen("fruit.in","r",stdin);
    //freopen("fruit.out","w",stdout);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    cout<<step(n);
    return 0;
}

这里才是真正的递归代码O(∩_∩)O哈哈~

来个简单的荔枝

~~kkksc03考前临时抱佛脚~~ 咦嘿嘿(^▽^) 、O(∩_∩)O哈哈~、o(^＠^)o

别走(ToT)/~~~憋走

最后讲一些些……

~~递归就剩一个优点——逻辑清晰（套话而已）代码简单（就是有点废人︿(￣︶￣)︿）~~

• 递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算，如f(n)=f(n-1)+f(n-2)的递归实现。

• 调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。

• 递归由于是函数调用自身，而函数调用是有时间和空间的消耗的，每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址以及临时变量，而往栈中压入数据和弹出数据都需要时间。

so：一般哈，一般情况下，递归的题（考试时），代码复杂，内存大，用时长，极为复杂，but是DFS的只因础，属于不会就废的内容︿(￣︶￣)︿。

递归