1. 递归(Recursion)
1.1 概念
递归是一种直接或者间接调用自身函数。
1.2 本质
把问题分解成规模缩小的同类问题的子问题
递归就是函数的“套娃”
1.3 套路
- 确定递归公式
- 确定边界条件
1.4 练习
- 递归打印
1~10 - 数组求和
- 阶乘
- 打印第
n个斐波那契数列
使用递归模拟
for循环(自增的i和不停的调用)。
在第一个月有一对刚出生的小兔子，在第二个月小兔子变成大兔子并开始怀孕，第三个月大兔子会生下一对小兔子，并且以后每个月都会生下一对小兔子。 如果每对兔子都经历这样的出生、成熟、生育的过程，并且兔子永远不死，那么兔子的总数是如何变化的？
1.5 原理解析
小知识
德罗斯特效应(Droste effect)是递归的一种视觉形式，是指一张图片的某个部分与整张图片相同，如此产生无限循环。
2. 迭代
2.1 概念
迭代（辗转法）是一种不断用变量的旧值递推新值的过程。
2.2 本质
迭代很多时候就是使用循环实现。
2.3 套路
int sum(int n ) {
int sum =0;
for(int i = 1 ; i <= n;i++) sum+=n;//求解1~n的和
return sum;
}
- 确定迭代变量：确定一个直接或间接地不断由旧值推断新值的变量，如
sum。 - 建立迭代关系式：从变量的旧值推断到新值的公式，如
。
- 对迭代过程进行控制：迭代不可能无限循环下去，需要对何时退出迭代进行控制，如
i=>n退出循环。
2.4 练习
- 递归打印
1~10 - 数组求和
- 阶乘
- 打印第
n个斐波那契数列
3. 递归与迭代比较
3.1 递归可能比较耗内存
实现函数printN(int n),打印从1到n的所有整数。
#include <stdio.h>
#include <stdlib.h>
#ifndef RECURSION
void printN(int n){
for(int i=1;i<=n;++i){
printf("%d\n",i);
}
}
#else
void printN(int n){
if(0 != n) {
printN(n-1);
printf("%d\n",n);
}
}
#endif
int main(int argc,char** argv) {
if(argc != 2){
printf("usage:%s <num>\n",argv[0]);
return 1;
}
printN(atoi(argv[1]));
return 0;
}
编译执行printN(int n)函数循环实现
gcc test.c && ./a.out 1000000
编译执行printN(int n)函数递归实现
gcc -DRECURSION test.c && ./a.out 1000000
3.2 递归可能比较效率低
斐波那契数列
- 递归
#include <stdio.h>
#include <stdlib.h>
#ifndef RECURSION
long long Fibonacci(int n) {
if(n < 1) return 0;
if(1 == n || 2 == n) return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}
#else
long long Fibonacci(int n) {
if(n<1) return 0;
long long a = 0;
long long b = 1;
for(int i=2;i<=n;i++){
b += a;
a = b - a;
}
return b;
}
#endif
int main(int argc,char** argv) {
if(argc != 2){
printf("usage:%s <num>\n",argv[0]);
return 1;
}
printf("%lld\n",Fibonacci(atoi(argv[1])));
return 0;
}
编译执行Fibonacci(int n)函数循环实现
gcc test.c && ./a.out 45
编译执行Fibonacci(int n)函数递归实现
gcc -DRECURSION test.c && ./a.out 45
命令time可以测量程序执行的时间。
练习：递归打印九九乘法表
void PrintCol(int r,int c){
if(0==c) return;
PrintCol(r,c-1);
printf("%d*%d=%2d ",r,c,r*c);
}
void PrintRow(int r){
if(0==r) return;
PrintRow(r-1);
PrintCol(r,r);
printf("\n");
}
禁止套娃
4. 动态规划
解决递归性能问题的一种方法。
70. 爬楼梯
- 递归：楼顶开始思考，自顶而下
class Solution {
public:
int climbStairs(int n) {
if(1==n||2==n) return n;
return climbStairs(n-1)+climbStairs(n-2);
}
};
递归超时，因为存在大量的重复计算。
- 动态规划之备忘录/记忆化
使用数组记录计算过程中的数值，避免重复计算。
class Solution {
public:
vector<int> dp; // 动态规划：备忘录/记忆化
int climbStairs(int n) {
if(dp.empty()) dp.resize(n+1);
if(1==n||2==n) return n;
if(0==dp[n]) dp[n] = climbStairs(n-1)+climbStairs(n-2);// 减少重复递归计算
return dp[n];
}
};
- 动态规划之自底而上
楼底开始思考，自底而上，迭代方式解决问题。
class Solution {
public:
int climbStairs(int n) {
if(1==n||2==n) return n;
int prev = 1; // 台阶1
int curr = 2; // 台阶2
for(int i=3;i<=n;++i){
int res = prev + curr;
prev =curr;
curr = res;
}
return curr;
}
};
练习
- 链表的顺序和逆序打印数据
- 链表的反序
