函数与递归
题单介绍
# 函数与递归
### 什么是函数？
- 系统函数
pow(a,b) $a^b$
sqrt(n) $\sqrt{n}$
sort(a+1,a+n+1) 排序
- 自定义函数
$$
n!=1\times 2\times 3\dots\times n
$$
```cpp
int jc(int n) {
int sum = 1;
for (int i = 1; i <= n ; i ++ ) sum*= i ;
return sum;
}
```
- 判断质数
```cpp
bool isprime(int x) {
if (x<2) return false;
if (x==2) return true;
if (x%2==0) return false;
for (int i = 3;i*i <= x ; i += 2)
if (x%i==0) return false;
return true;
}
```
- 十进制转其他进制
```cpp
string tentoother(int n,int k) {
string str = "";
while (n>0) {
if (n%k<10) str = char(48+n%k)+str;
else str = char(55+n%k) + str;
n/=k;
}
return str;
}
```
- 其他进制转十进制
```cpp
int othertoten(int k,string str) {
int sum = 0 ;
for (int i = 0 ; i < str.size() ; i ++ ) {
sum*= k;
if (str[i]>='A') sum += str[i]-'A'+10;
else sum += str[i]-48;
}
return sum;
}
```
- 判断回文数
```cpp
bool pdhw(string str) {
string res = str;
reverse(res.begin(),res.end());
return res == str;
}
```
```cpp
bool pdhw(string str) {
int l = 0 , r = str.size()-1;
while (l<=r) {
if (str[l]==str[r]) l ++, r--;
else return false;
}
return true;
}
```
### 无返回值的函数(过程）
## 递归
将原问题拆分成更小的子问题，子问题还可以继续拆分直到可以直接解决。
### 例题1：阶乘问题
$$
f(n)=n!=1\times 2\times 3\dots\times n
$$
$$
f(n)=f(n-1)\times n
$$
```cpp
int f(int n)
{
if (n==1) return 1;
return f(n-1)*n;
}
```
### 例题2：斐波那契问题（爬楼梯问题）
递推：是顺向思维
递归：是逆向思维
如果你在n层，你上一步可能在哪些层？$n-1,n-2$.
$$
f(n)=f(n-1)+f(n-2),f(1)=1,f(2)=2
$$
```cpp
int f(int n) {
if (n==1||n==2) return n;
return f(n-1)+f(n-2);
}
```