斐波那契和汉诺塔实现递归算法

朱雀 2023-07-06 14:53 36阅读 0赞

## 递归 ##

递归的意思就是一个函数在自己内部不断调用自己的过程，通过反复调用，可以用步步蚕食的方法，解决掉一个比较复杂的问题。总之的递归的核心在于分而治之的思想，在大的问题中发现规律，把体量较大的问题分割开，从问题最小的部分入手，由小到大，逐步解决问题。  
相信好多人第一次看递归的代码都觉得，这个代码不复杂啊，才几十行而已，但是细读发现并不好理解，这也正是递归的特点，由于在函数中调用函数本身，往往不容易看懂递归的终止条件。  
下面通过两道经典问题来具体解释一下递归的精髓：

## 1、汉诺塔问题 ##

这道题目可以说是递归思想最经典的体现：[原题入口][Link 1]  
汉诺塔是一种古老的游戏。  
一共3个柱子，标号为1,2,3  
1号柱子有从大到小一共n个盘子。  
每次移动最上方的一个盘子，可以移动到其他的柱子。  
任何一个盘子，都不能叠在比它更小的盘子的上方。  
请把盘子从1号柱子，全部移动到3号柱子。  
起始：  
移动到这样：  
现在，给出了n个盘子，请你描述一下用最短次数移动的过程。

移动步骤：  
（1）先把n-1个盘子由1——2，大的在下，小的在上；  
（2）再将1号柱的第n个盘子移动到3柱；  
（3）最后把2柱的剩余盘子借助1柱移到3柱  
以上步骤实际上是一个重复的过程，则整个问题可以使用递归解决，当盘子个数为1时直接移动即可，为n时则先借助一根针将n-1个盘子移动到另一根针上，而n-1根针可以先移动n-1-1根针，如此往复。

void move(int n, char x1, char x2, char x3) { 
        // 将n个盘子从1柱借助2移动到3上
        if (1 == n) { 
            cout << x << "-->" << z << endl;
        } else { 
            // 将n-1个盘子从1柱借助3移动到2上
            move(n - 1, x, z, y);
            // 将第n个盘子从1移动到3上
            cout << x << "-->" << z << endl;
            // 将n-1个盘子从2借助1移动到3上
            move(n - 1, y, x, z);
        }
    }

## 2、斐波那契数列 ##

斐波那契数列当n>3时，第n个元素的值等于第n-1个元素和n-2个元素的和，当n不确定具体数值时，可以通过递归的方式实现，先给定前两个元素的值1，从第三位开始递归

int Fib(int n) { 
        if (n < 2)
            return 1;
     
        return Fib(n - 1) + Fib(n - 2);
    }

[Link 1]: https://www.dotcpp.com/oj/problem2056.html