# 递归的思想

# 数线段

问题：不在同一直线上的四点最多可以画几条线段？ 解题：如果是3个点，明显只能画三条线段。

如果增加1个点，变成4个点，那么新增的1个点，可以与原有的3个点分别连接，增加了3条线段,所以就是一共是6条线段。

如果5个点呢？比4个点多了一个点，与之前的4个点分别连接，增加了4条线段,所以就是一共是10条线段

求解的过程展示如下

# 另一个例子

假设你在一个电影院，你想知道自己坐在哪一排，但是前面人很多，你懒得去数了，于是你问前一排的人「你坐在哪一排？」，这样前面的人 (代号 A) 回答你以后，你就知道自己在哪一排了——只要把 A 的答案加一，就是自己所在的排了。不料 A 比你还懒，他也不想数，于是他也问他前面的人 B「你坐在哪一排？」，这样 A 可以用和你一模一样的步骤知道自己所在的排。然后 B 也如法炮制。直到他们这一串人问到了最前面的一排，第一排的人告诉问问题的人「我在第一排」。最后大家就都知道自己在哪一排了。

# 递归问题的核心

一个合法的递归定义包含两个部分：基础情况和递归部分。

分析一个递归问题就是列出递归定义表达式的过程。 数线段问题的表达式可以列为 $f(n)=\begin{cases} 1 &\text{if } \quad n=2 \\ n-1+f(n-1) &\text{if } \quad n>2 \end{cases}$

上面那个电影院排数的问题表达式可以列为：

$f(n)=\begin{cases} 1 &\text{if } \quad n=1 \\ 1+f(n-1) &\text{if } \quad n>1 \end{cases}$

# 使用递归方法计算线段个数

这是一段根据节点数量，计算节点构成线段数量的程序，运用了递归的思想。 我们知道：

• 当节点数为2的时候，构成的线段数量为1
• 当节点数为3的时候，构成的线段数量为2+1
• 当节点数为4的时候，构成的线段数量为3+2+1
• 当节点数为N的时候，构成的线段数量为n-1+"n-1"个节点构成的线段数量

归纳如下： f(n) = n-1 + f(n-1),特别的当n<1时候，不能构成线段，当n=2的时候，线段数量为1

import argparse

#主程序
def main():
    #解析命令行参数
    parser = argparse.ArgumentParser()
    #参数格式
    parser.add_argument("--num","-n",required=True,help="node number")
    args = parser.parse_args()
    #参数赋值
    nodeNum = int(args.num)
    #计算
    result = calSegNum(nodeNum)
    #输出
    print("When node number is: " + str(nodeNum), "line segment number is: " + str(result))

#递归计算程序
def calSegNum(nodeNum):
    #不能小于1
    if nodeNum <= 1:
        print("node Num at least is 2")
        exit(0)
    #等于2时，线段数量为1
    elif nodeNum == 2:
        return 1
    else:
        return (nodeNum-1 + calSegNum(nodeNum-1))


if __name__=="__main__":
    main()

# 使用递归思想解决汉诺塔问题

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘

如果用递归的思想怎么解决呢？

假设为5个圆盘,初始情况如下：

如果要想把A全部移动到C，那么就要先移动4个圆盘到B，变为下图

继续思考，如果要把4个圆盘移动到B，那么必须先要把3个圆盘移动到C

如果要把3个圆盘移动到C，那么必须先要把2个圆盘移动到B

如果要把2个圆盘移动到B，那么必须先要把1个圆盘移动到C

可以发现:

• 如果A为起始，C为目标，那么B为临时用作交换区
• 如果A为起始，B为目标，那么C为临时用作交换区
• 如果B为起始，C为目标，那么A为临时用作交换区
• 如果B为起始，A为目标，那么C为临时用作交换区
• 如果C为起始，B为目标，那么A为临时用作交换区
• 如果C为起始，A为目标，那么B为临时用作交换区

当成为第一个图的样子后，就可以把B的4个盘子移动到C了。

这是我们发现，B成了起始点，C为目标。如要把B的四个盘子移动到C,就要把先移动3个盘子到A

对上面的图总结发现，可以把这个任务分解为3个步骤

• 移动n-1个盘子到B
• 移动1个盘子到C
• 移动n-1个盘子到C

对于移动n-1个盘子到B这个过程

• 则必须先移动n-2个盘子到C
• 移动1个盘子到B
• 移动n-2个盘子到B

这就是典型的递归解决的方式

现在可以编写代码如下

def move_disks(_from, _to, _num):
    if _num == 0:
        return
    if _from == "A" and _to == "C":
        tmp = "B"
    if _from == "A" and _to == "B":
        tmp = "C"
    if _from == "B" and _to == "C":
        tmp = "A"
    if _from == "B" and _to == "A":
        tmp = "C"
    if _from == "C" and _to == "B":
         tmp = "A"
    if _from == "C" and _to == "A":
         tmp = "B"
    move_disks(_from, tmp, _num - 1)
    print("move 1 plate from: "+ _from + " to: " + _to)
    move_disks(tmp, _to, _num - 1)


if __name__ == '__main__':
    move_disks("A","C",5)

运行结果如下

move 1 plate from: A to: C
move 1 plate from: A to: B
move 1 plate from: C to: B
move 1 plate from: A to: C
move 1 plate from: B to: A
move 1 plate from: B to: C
move 1 plate from: A to: C