递归基本思想

递归的两大要素：

递推关系：

根据某种方法，对问题进行拆分【递】

终止条件：

到达某种条件，问题可以直接求解，此时到达递归的边界，然后依次组合出原来的大问题的解。【归】

代码讲解：

2404：

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

$f(n)$表示前n个数的和
递推关系：$f(n)=f(n-1)+n$
边界:$f(1)=1$

2462:

#include<iostream>
typedef unsigned long long ull;
using namespace std;
int n,cnt,m,a[100000];
int f(int n){
	if(n==1) return a[1];
	return max(f(n-1),a[n]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cout<<f(n);
}

$f(n)$表示前n个数的最大值
递推：$f(n)=\max(f(n-1),a[n])$
边界：$f(1)=a[1]$

斐波那契数列：

普通算法：

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

时间复杂度$O(2^n)$

but,why???
because :

递归过程中有大量的重复计算，例如上图f(n-2)被算了很多次。

我们可以通过记忆化来避免重复计算，即定义一个数组存。
记忆化：

int f(int n){
  if(j[n]!=0) return j[n];
  if(n==1||n==2) return 1;
  j[n]=f(n-1)+f(n-2);
  return f(n-1)+f(n-2)
}

2458:
题目：

f(n)表示数字 n 各个位数上的和

递推： f(n)=f(n/10)+n%10

边界：

$n>10$时 return n;

代码：

#include<iostream>
typedef unsigned long long ull;
using namespace std;
int n,cnt,m,a[100000];
int f(int n){
	if(n<10) return n;
	return f(n/10)+n%10;
}
int main(){
	cin>>n; 
	cout<<f(n);
}

3831:

#include<iostream>
typedef unsigned long long ull;
using namespace std;
int n,cnt,m;
string s;
bool f(int i){
	if(i==s.size()/2) return true;
	if(s[i]!=s[s.size()-1-i]) return false;
	return f(i+1); 
}
int main(){
	cin>>s; 
	if(f(0)==1) cout<<"是回文串";
	else cout<<"不是回文串"; 
}

我的代码：
f(i)表示s[i]~s[s.size()-1-i]是否是回文
递推：

if(i==s.size()/2) return true;
if(s[i]!=s[s.size()-1-i]) return false;
边界：

if(i==s.size()/2) return true;

#include<iostream>
typedef unsigned long long ull;
using namespace std;
int n,cnt,m;
string s;
bool f(int i){
	if(i==s.size()/2) return true;
	if(s[i]!=s[s.size()-1-i]) return false;
	return f(i+1); 
}
int main(){
	cin>>s; 
	if(f(0)==1) cout<<"是回文串";
	else cout<<"不是回文串"; 
}

老师的代码：

#include<iostream>
typedef unsigned long long ull;
using namespace std;
int n,cnt,m;
string s;
bool f(int i,int j){
	if(i>=j) return true;
	if(s[i]==s[j]) return f(i+1,j-1);
	return false;
}
int main(){
	cin>>s; 
	if(f(0,s.size()-1)==1) cout<<"是回文串";
	else cout<<"不是回文串"; 
}

其实也差不多。。。