递归的应用-汉诺塔游戏

汉诺塔游戏：有A、B、C三个柱子，A柱子上有n个盘片，要求把A柱子上的盘片通过B柱子移动到C柱子，规则是“小盘片只能在大盘片的上边”。

思路：把A柱上所有的盘子分成两部分，把上面的n-1个盘子看成一个整体，这样就简化成了两个盘子（上面的n-1个，和最下面的1个）
1. 先把A柱的n-1个盘(看成一个整体)，通过C盘移动到B盘
2. 然后把A柱最后一个盘移动到C盘
2. 最后把B柱的n-1个盘通过A盘移动到C盘

Python版本：

def move(n, a, b, c):
    """
    递归的应用
    汉诺塔游戏：有A、B、C三个柱子，A柱子上有n个盘片，要求把A柱子上的盘片通过B柱子移动到C柱子，规则是“小盘片只能在大盘片的上边”。
    :param n: a柱中的盘片数量
    :param a: a柱的名称
    :param b: b柱的名称
    :param c: c柱的名称
    :return:
    """
    if n == 1:
        # 如果只有一个，则直接把它从a柱移动到$c柱，打印出a柱移动到c的盘片
        print(a, '-->', c)
    else:
        # 否则，先把a柱上面的n-1个通过c柱移动到b
        move(n-1, a, c, b)
        # 打印出a移动到c的盘片
        print(a, '-->', c)
        # 最后把b中的n-1个盘片移动到c
        move(n-1, b, a, c)


# 调用，共3个盘片，第一个盘片叫A，第二个盘片叫B，第三个盘片叫C
move(3, 'A', 'B', 'C')

php版本：

<?php
    /**
     * 递归的应用
     * 汉诺塔游戏：有A、B、C三个柱子，A柱子上有n个盘片，要求把A柱子上的盘片通过B柱子移动到C柱子，规则是“小盘片只能在大盘片的上边”。
     * @param $n $a柱中的盘片数量
     * @param $a $a柱的名称
     * @param $b $b柱的名称
     * @param $c $c柱的名称
     */
    function hanoi ($n, $a, $b, $c)
    {
        if ($n == 1) {
            //如果只有一个，则直接把它从$a柱移动到$c柱，打印出$a柱移动到$c的盘片
            echo $a, '-->', $c , "\n";
        } else {
            //否则，先把$a柱上面的n-1个通过$c柱移动到$b
            hanoi($n - 1, $a, $c, $b);
            //打印出$a移动到$c的盘片
            echo $a, '-->', $c , "\n";
            //最后把$b中的n-1个盘片移动到$c
            hanoi($n - 1, $b, $a, $c);
        }
    }

    //调用，共3个盘片，第一个盘片叫A，第二个盘片叫B，第三个盘片叫C
    hanoi(3, 'A', 'B', 'C');

js版本：

/**
 * 递归的应用
 * 汉诺塔游戏：有A、B、C三个柱子，A柱子上有n个盘片，要求把A柱子上的盘片通过B柱子移动到C柱子，规则是“小盘片只能在大盘片的上边”。
 * @param n a柱中的盘片数量
 * @param a a柱的名称
 * @param b b柱的名称
 * @param c c柱的名称
 */
function hanoi (n, a, b, c){
    if(n==1){
        //如果只有一个，则直接把它从a柱移动到$c柱，打印出a柱移动到c的盘片
        console.log(a, '-->', c);
    }else{
        //否则，先把a柱上面的n-1个通过c柱移动到b
        hanoi(n-1, a, c, b);
        //打印出a移动到c的盘片
        console.log(a, '-->', c);
        //最后把b中的n-1个盘片移动到c
        hanoi(n-1, b, a, c);
    }
}

//调用，共3个盘片，第一个盘片叫A，第二个盘片叫B，第三个盘片叫C
hanoi(3, 'A', 'B', 'C');