数据结构之递归算法

斐波那契（Fibonacci）的递归实现

迭代思想

#include <iostream> using namespace std; int main() { int i; int a[40]; a[0] = 0; a[1] = 1; for (i = 2; i < 40; i++) { a[i] = a[i - 1] + a[i - 2]; } for (i = 0; i < 40; i++) { cout << a[i] << " "; } return 0; }

递归事实上就是函数自己调用自己，我们先一起看下代码的实现，然后再来分析：

int Fib(int i) { if (i < 2) return i == 0 ? 0 : 1; return Fib(i - 1) + Fib(i - 2); }

例如 i=5 的时候，不停地调用自身，只有当 i=0,1 时才可以计算结果。 在高级语言中，函数调用自己和调用其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。 迭代使用的是循环结构，递归使用的是选择结构。 编写一个递归函数，实现将输入的任意长度的字符串反向输出的功能。例如输入字符串FinshC,则输出字符串ChsniF。 同学们一般会采用将该字符串存放到一个数组中，然后将数组元素反向的输出即可。这道题要求输入是任意长度，所以不用递归的话，实现起来会比较麻烦。 我们说过，递归它需要有一个结束的条件，那么我们可以将“#”作为一个输入结束的条件。

void print() { char a; cin >> &a; if (a != '#') print(); if (a ！= '#') cout<<a; }

汉诺塔

这其实也是一个经典的递归问题。

#include <iostream> using namespace std; //将 n 个盘子从 x 借助 y 移动到 z void move(int n, char x, char y, char z) { if (1 == n) { cout << x << "->" << z << endl; } else { move(n - 1, x, z, y);//将n-1个盘子从x借助z移到y上 cout << x << "->" << z << endl;//将第n个盘子从x移到z上 move(n - 1, y, x, z);//将n-1个盘子从y借助x移到z上 } } int main() { int n; char x; char y; char z; cout << "请输入汉诺塔的层数："; cin >> n; cout << endl << "移动的步骤如下" << endl; move(n, 'x', 'y', 'z'); return 0; }

八皇后问题

未完待续