0x01 递归

本章浅析递归,笔者在学习递归的时候,也曾绕了很大一个圈子,老是往复杂的方面去想,如递归内部每一步是怎么运行
结果绕着绕着就绕晕了,导致给我的感觉是,递归很难懂
简而言之,递归即是函数自己调用自己,它解决了我们很难思考的问题,将问题大而化小
使用递归:
    1.必须有退出条件,不能无限循环
    2.必须保证递归后,算法简化
编写递归函数:
    1.编写语句解决分解后的每个小问题(先假设递归函数已经可以使用)
    2.在函数开头编写分支,用来处理不能分解的情况,这个分支保证函数可以结束

0x02 Demo:计算从1开始到给定某个正整数的值(1+2+3+……)

第一步假设递归函数 sum 可以使用:sum(num - 1)
   如果给定的正整数是3,那么 sum(3 - 1) 即2,最后在加上num 即 sum(num - 1) + num 得 2 + 3.
第二步分解不了的情况:传入的结果为 1,那么就返回1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//demo
#include "stdio.h"

int sum(int num){
if( num == 1 ){
return 1;
}
return sum(num - 1) + num;
}

int main(){
printf("1+2+3+……的和是:%d\n",sum(10));
return 0;
}

0x03 汉诺塔

汉诺塔做为一个经典的递归练习程序,几乎所有学递归都逃不过这个程序
那么什么是汉诺塔,详情见汉诺塔词条
汉诺塔程序解读:
1.假设有三根柱子 A,B,C
2.A 柱子上有若干个圆盘,从大到小依次排列
3.汉诺塔问题,将A柱子的所有圆盘移动到C柱子上
汉诺塔规则:
1.一次只能移动一个圆盘
2.大的圆盘不能放在小圆盘上
递归分解:
1.分解不了的情况,即只有一个圆盘,直接从A移动到C
2.假设有两个或多个圆盘,这里统一把所有圆盘看成2个圆盘,即第2圆盘和第2-1个圆盘(n和n-1).
使用递归完成问题:
1.把A柱子上的第n-1个圆盘,移动到B柱子上
2.把A柱子上的第n个圆盘,移动到C柱子上
3.把B柱子上的第n-1个圆盘,移动到C柱子上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//demo
#include "stdio.h"
void hanoi(int n,char A,char B,char C){
if(num == 1){
printf("%c -> %c\n",A,C);
}else{
hanoi(n-1,A,C,B)
printf("%c -> %c\n",A,C);
hanoi(n-1,B,A,C);
}

}
int main(){
hanoi(3,'A','B','C');
return 0;
}

result:
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C