递归学习

今天学长教了递归，下面说说我对递归的一些理解。

以下面这个题目为例：

题目描述

Ø例5.2 求Fibonacci数列问题。
─斐波那契数列指的是这样一个数列：
─0、1、1、2、3、5、8、13、21、……
─F[0]=0, F[1]=1, F[i]=F[i-1]+F[i-2], i>=2;
编程输出前n个Fibonacci数

输入

输入n

输出

输出前n个Fibonacci数

样例输入

样例输出

0
1
1
2
3


当求F[5]时，它们的层数关系如下：

求F[5]时就要知道F[4]和F[3]的值，而F[4]的值等于F[3]+F[2]，F[3]的值等于F[2]+F[1]，依次递归下去，由于F[1]和F[0]的值知道，所以直到等于F[1]或F[0]时递归结束。

具体代码如下：

 1 #include <iostream>
 2 using namespace std;
 3  
 4 int f(int x){
 5     if(x == 0){
 6         return 0;
 7     }
 8     else if(x == 1){
 9       return 1;
10     }
11     else return f(x-1)+f(x-2);
12 }
13 int main(){
14     int n;
15     cin >> n;
16     for(int i = 0; i < n; i++){
17         cout << f(i) << endl;
18     }
19     return 0;
20 }

类似的递归问题还有：

题目描述

对1~ n 的 n个整数进行全排列(n<=9),编写程序输出所有可能的排列组合. 用递归算法实现.

输入

输入n

输出

输入n个整数的所有可能的排列组合.

样例输入

样例输出

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 void f(int arr[], int k, int m){
 6     if(k == m){
 7         for(int i = 0; i <= m; i++){
 8             printf("%4d",arr[i]);
 9         }
10         printf("
");
11     }
12     else{
13         for(int i = k; i <= m; i++){
14             swap(arr[i], arr[k]);
15             f(arr, k+1, m);
16             swap(arr[i], arr[k]);
17         }
18     }
19 }
20 int main(){
21     int n;
22     cin >> n;
23     int a[11];
24     for(int i = 0; i < n; i++)
25         a[i] = i+1;
26     f(a,0,n-1);
27     return 0;
28 }

题目描述

汉诺（Hanoi）塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有n个盘子，盘子大小不等，大的在下，小的在上（如图）。有一个和尚想把这n个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求打印移动的步骤。如果只有一个盘子，则不需要利用B座，直接将盘子从A移动到C。

输入

输入盘子个数n

输出

输出盘子最少移动的步骤

样例输入

样例输出

1:A->C
2:A->B
3:C->B
4:A->C
5:B->A
6:B->C
7:A->C

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 void move(char x, char y);
 5 void f(int n, char a, char b, char c){
 6     if(n == 1)
 7         move(a, c);
 8     else{
 9         f(n-1,a,c,b);
10         move(a,c);
11         f(n-1,b,a,c);
12     }
13 }
14 void move(char x, char y){
15     static int i = 1;
16     printf("%d:%c->%c
",i++,x,y);
17 }
18 int main(){
19     int n;
20     cin >> n;
21     f(n, 'A', 'B','C');
22     return 0;
23 }

题目描述

八皇后问题
是一个古老而著名的问题，是回溯算法的典型案例。
该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出的，在8*8格的国际象棋上摆放八个皇后;使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上;
问有多少种摆法, 输出所有可能的解？

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 using namespace std;
 5 const int N = 8;
 6 int a[N][N] = {0};
 7 void Print(){
 8     static int ans = 1;
 9     printf("Case %d:
",ans++);
10     for(int i = 0; i < N; i++){
11         for(int j = 0; j < N; j++){
12             printf("%c ",a[i][j]?'Q':'.');
13         }
14         printf("
");
15     }
16     printf("
");
17 }
18 bool Safety(int row, int col){
19     for(int i = 0; i < row; i++){
20         for(int j = 0; j < N; j++){
21             if(a[i][j]&&(j==col||abs(row-i)==abs(col-j)))
22                 return false;
23         }
24     }
25     return true;
26 }
27 void BlackTrack(int i){
28     if(i >= N){
29         Print();
30         return;
31     }
32     else{
33         for(int j = 0; j < N; j++){
34             a[i][j] = 1;
35             if(Safety(i,j)){
36                 BlackTrack(i+1);
37             }
38             a[i][j] = 0;
39         }
40     }
41 }
42 int main(){
43     BlackTrack(0);
44     return 0;
45 }

输入

没有输入

输出

输出所有可能的解