算法--递归

在编程中使用递归非常普遍，递归在计算机中通过栈来实现

递归的用处非常大

最简单就是阶乘的计算了

#include<iostream>
using namespace std;
int f(int n)
{
    if(n==1)
    return n;
    else
    return n*f(n-1);
}
int main() 
{
    int n,sum;
    cin>>n;
    cout<<f(n)<<endl;
    return 0;
}

还有一个经典就是汉诺塔问题了

设 a,b,c 是 3 个塔座。开始时，在塔座 a 上有一叠共 n 个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为 1,2,…,n,现要求将塔座 a 上的这一叠圆盘移到塔座 b 上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：

规则 1：每次只能移动 1 个圆盘；

规则 2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；

规则 3：在满足移动规则 1 和 2 的前提下，可将圆盘移至 a,b,c 中任一塔座上。

将a塔上的移到c

求需要移动多少次？

这个问题咋一看，会没有头绪

仔细想想就会发现要完成移动n个圆盘就得完成移动n-1个

完成移动n-1个圆盘就得完成移动n-2个

可以找出递推公式  f（n）=f（n-1）*2+1；

#include<iostream>
using namespace std;
int f(int n)
{
    if(n==1)
    return n;
    else
    return 2*f(n-1)+1;
}
int main()
{
    int n;
    cin>>n;
    cout<<f(n)<<endl;
    return 0;
 } 

加个汉诺塔的具体实现过程

#include<iostream>
using namespace std;
void move(int i,char a,char c)
{
    cout<<i<<" "<<a<<"->"<<c<<endl;
}
int f(int i,char a,char b,char c)
{
    if(i==1)
    move(i,a,c);
    else
    {
      f(i-1,a,c,b);
      move(i,a,c);
      f(i-1,b,a,c);
    }
}
int main()
{
    int n;
    cin>>n;
    f(n,'a','b','c');
    return 0;
 } 

递归还有非常多的应用，想到再来更新

————————————————————————————————————————更新了

https://www.nowcoder.com/practice/f74c7506538b44399f2849eba2f050b5?tpId=61&tqId=29557&tPage=3&ru=%2Fkaoyan%2Fretest%2F1002&qru=%2Fta%2Fpku-kaoyan%2Fquestion-ranking

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#define inf 1006
using namespace std; 
int dp(int m,int n)
{
    if(m>n)
    return 0;
    else
    return dp(m*2,n)+dp(m*2+1,n)+1;
}
int main()
{
    int n,m;
    cin>>m>>n;
    cout<<dp(m,n)<<endl;
    return 0;
}

 ————————又来更新了————————————
https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&tqId=29483&tPage=1&ru=%2Fkaoyan%2Fretest%2F1001&qru=%2Fta%2Ftsing-kaoyan%2Fquestion-ranking

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
string s;
int i=0,n;
struct node{
    char c;
    struct node *lchild;
    struct node *rchild;
    node(char c):c(c),lchild(NULL),rchild(NULL){}
};
node* creat_tree()
{
    char c=s[i++];
    if(c=='#')
    return NULL;
    node* root=new node(c);
    root->lchild =creat_tree();
    root->rchild =creat_tree();
    return root;
}
void pre_order(node *root)
{
    if(!root)
    return ;
    pre_order(root->lchild);
    printf("%c ",root->c);
    pre_order(root->rchild);
}
int main()
{
    cin>>s;
    n=s.size();
    node *root=creat_tree();
    pre_order(root);
    return 0;
}

一些递归题目和dp确实有相似之处