递归

关于函数递归的一些总结

核心思想便是找到解决问题时出现的相似的步骤，用递归的思想去解决问题，
递归的过程就像是将大的问题分解为小的，一步步类似的问题，交给电脑去递归。

题目
1.更相减损术
2小q的数列
3The Biggest Water Problem
4.下台阶问题
5.汉诺塔问题，以及用二进制的思想解决汉诺塔问题

最简单的函数递归的例子便是算n的阶乘：

int factorial(int x) //这样一个简单的函数便能帮助我们求x的阶乘。
{
	if(x==1)	return 1; //边界条件：阻止函数无限递归下去
	return x*factorial(x-1); //递归调用
}

然后便是下台阶问题， 一共有n级台阶，每次可以选择下一级或是两级，一共有多少种走法？
解决问题的核心便是将问题拆分成可循环的一个个小问题，思考第一步怎么走，第一步可以选择下一级，也可以选择下两级，那么走n级台阶的问题会被拆分成走（n-1）级台阶和走（n-2）级台阶走法和的问题
类似的走（n-1）级台阶也会被拆成(n-2)和(n-3）的走法和，于是我们就得到了递归调用的部分

return f(n-1) + f(n-2);

为了阻止函数无限调用下去，边界条件应设为

if(n==1)	return 1;
if(n==2)	return 2;

于是完整代码

int int f(int n)
{
	if(n==1)	return 1;
	if(n==2)	return 2;
	return f(n-1) + f(n-2);
}

更相减损术

#include<bits/stdc++.h>

using namespace std;

long long yue( long long n1, long long n2)
{
    n1 = n1-n2;
    if(n1==n2 || n1==1)    return n1;
    return yue(max(n1,n2),min(n1,n2));
}
int main()
{
    long long n1, n2;
    cin >> n1 >> n2;
    cout << yue(max(n1,n2),min(n1,n2));
    return 0;
}

小q的数列

记得用long long,并且最后输出是找规律

#include<bits/stdc++.h>
#include<cmath>

using namespace std;

long long get_(long long n)
{
    if(n==1)    return 1;
    if(n==0)    return 0;
    if(n>=2)    return get_(n/2)+get_(n%2);
    return 0;
}

long long find_(long long n, long long t)
{
    for( long long i=1; i<=t; i++)
    {
        if( get_(i)==n)
            return i;
    }
    return 0;
}
int main()
{
    long long t;
    cin >> t;
    for( long long i=1; i<=t; i++ )
    {
        long long n;
        cin >> n;
        cout << get_(n) << " " << (long long)(pow(2,get_(n))-1) << endl;
    }
    return 0;
}

最后利用二进制的思想解决汉诺塔问题间b站视频