浅谈python中的递归

--------------python 环境为3.6.4-------- 下面为高手写的代码
def move(n, a, b, c):
	if n == 1:
		return print(a, '-->', c)
	move(n-1,a,c,b)
	move(1,a,b,c)
	move(n-1,b,a,c)
----------------------------------------------
	乍一看真的是一个很简单很简单的三层递归函数。我第一眼看到的时候都不认为这个是对的。但是真的执行以后发现。写的很有道理。输入2和3执行一下。发现都能出来。
>>> move(2,'a','b','c')
a --> b
a --> c
b --> c
>>> move(3,'a','b','c')
a --> c
a --> b
c --> b
a --> c
b --> a
b --> c
a --> c


直接看，我的水平着实有限，所以打算拆开来一步步看。首先改写一下格式。我准备一个一个拆分来看。首先将第一个递归拆出来。带入几个值看一下
def move(n, a, b, c):
    if n == 1:
        return print(a, '-->', c)
    move(n-1,a,c,b)	
>>> move(2,'a','b','c')
a --> b
>>> move(3,'a','b','c')
a --> c
>>> move(4,'a','b','c')
a --> b
>>> move(5,'a','b','c')
a --> c
发现了一个很有意思的结果，就是在输入值(n>=2)且n为偶数的时候 是 a --> b,输入值为奇数的时候 是 a --> c。原因也很简单。在这个函数做递归的时候，因为n不等于1，所以递归函数一直在自己调用自己。所以字符 b和c的位置一直在互换。  

继续拆分。
def move(n, a, b, c):
    if n == 1:
        return print(a, '-->', c)
    move(1,a,c,b)
>>> move(2,'a','b','c')
a --> b
>>> move(3,'a','b','c')
a --> b
>>> move(4,'a','b','c')
a --> b
因为，这个n值为定值1.所以无论n(n>=2)值输入的值为何值都只会输出 a --> b。

最后拆分最后一个递归函数来看，
def move(n, a, b, c):
	if n == 1:
		return print(a, '-->', c)
	move(n-1,b,a,c)
	根据之前的两个可以想象得出来，这个函数在n(n>=2)输入奇数和偶数的时候输出值一定不一样。这里不做多解释。
>>> move(2,'a','b','c')
b --> c
>>> move(3,'a','b','c')
a --> c
>>> move(4,'a','b','c')
b --> c
>>> move(5,'a','b','c')
a --> c



接着如果两两结合呢。
执行 n=2、3、4的结果分别为：
def move(n, a, b, c):
    if n == 1:
        return print(a, '-->', c)
    move(n-1,a,c,b)
	move(1,a,b,c)
>>> move(2,'a','b','c')
a --> b
a --> c
>>> move(3,'a','b','c')
a --> c
a --> b
a --> c
>>> move(4,'a','b','c')
a --> b
a --> c
a --> b
a --> c
一旦开始两两结合。立马开始变得复杂了，这里有如下几种可能：
1 顺序执行，即传输一个值进去，会完整的走一次函数。
如果传输值为2，执行move(2-1,a,c,b) return ，move1。输出结果为如上所示。
如果传输值为3，则执行为，move(3-1,a,c,b) pass, move1, move(2-1,a,c,b) return, move(1,a,b,c)。 输出结果为如上所示
如果传输值为4，则执行为，move(4-1,a,c,b) pass,move1,move(3-1,a,c,b),move1,move(2-1,a,c,b) return,move(1,a,b,c)。 这里很明显输出结果并不是这样的。所以并不是顺序执行这种。

2 组内循环，即传输一个n值进去，在带有n值运算的条件中，一直循环调用到能return时再跳出当前循环。我认为这种方式应该是正确的。(句末带--为输出行，代码中abc为实际代表的abc)
如输入的n为2，则
move(2,a,b,c)
	move(1,a,c,b)--return跳出当前循环，abc值为上一层所变化的值
move(1,a,b,c)--
输出结果为: a-b a-c
输入的n为3，则
move(3,a,b,c)
	move(3-1,a,c,b)
		move(3-1-1,a,b,c)--return跳出当前循环，abc值为上一层所变化的值
	move(1,a,c,b)--
move(1,a,b,c)	--
输出结果为 : a-c a-b a-c 
输入n为4，则
move(4,a,b,c)
	move(4-1,a,c,b)
		move(4-1-1,a,b,c)
			move(4-1-1-1,a,c,b)-return跳出当前循环，abc值为上一层所变化的值
		move(1,a,b,c)--
	move(1,a,c,b)--
move(1,a,b,c)--
输出结果为：a-b a-c a-b a-c 
这类型的递归类似于一个凹字。




两两结合还有一种情况就是：这类的循环是先做一次 move1 然后做 move n 时会去调用move1。结果如下所示。
def move(n, a, b, c):
    if n == 1:
		return print(a, '-->', c)
	move(1,a,b,c)
    move(n-1,a,c,b)
执行 n=2、3、4的结果分别为：
>>> move(2,'a','b','c')
a --> c
a --> b
>>> move(3,'a','b','c')
a --> c
a --> b
a --> c
>>> move(4,'a','b','c')
a --> c
a --> b
a --> c
a --> b

这种情况下如果n为2 
move(2,a,b,c)
	move(1,a,b,c)--
	move(2-1,a,c,b)--
输出结果为：a-c a-b
n为3则
move(3,a,b,c)
move(1,a,b,c)--
	move(3-1,a,c,b)
		move(1,a,c,b)--
			move(3-1-1,a,b,c)--
输出结果为 a-c a-b a-c 
n为4则
move(4,a,b,c)
	move(1,a,b,c)--
	move(4-1,a,c,b)
		move(1,a,c,b)--
			move(4-1-1,a,b,c)
				move(1,a,b,c)--
					move(4-1-1-1,a,c,b)--
输出结果为:a-c a-b a-c a-b
这类型的递归类似于一个不断增加的直线（语言很笨拙）


两两结合最后一种情况如下所示：这类递归中，会先调用n-1，然后，后续函数在当前循环中使用n-1后的值。一组递归函数完成之后。重新调用第二组时,会重新初始化输入值。
def move(n, a, b, c):
    if n == 1:
            return print(a, '-->', c)
    move(n-1,a,c,b)
    move(n-1,b,a,c)
>>> move(2,'a','b','c')
a --> b
b --> c
>>> move(3,'a','b','c')
a --> c
c --> b
b --> a
a --> c
>>> move(4,'a','b','c')
a --> b
b --> c
c --> a
a --> b
b --> c
c --> a
a --> b
b --> c

如果输入的n为2
move(2,a,b,c)
	move(2-1,a,c,b)--循环1 
	move(2-1,b,a,c)--循环2 
输出结果为： a-b a-c	
如果输入的n为3
move(3,a,b,c)
	move(3-1,a,c,b)
		move(3-1-1,a,b,c)--
	move(3-1-1,b,a,c)--循环1结束
	move(3-1,b,a,c)#2组循环开始循环2为2时
		move(3-1-1,b,c,a)--
	move(3-1-1,a,b,c)--
输出结果为：a-c b-c b-a c-a
如果输入的n为4
move(4,a,b,c)
	move(4-1,a,c,b)
		move(4-1-1,a,b,c)
			move(4-1-1-1,a,c,b)--
		move(4-1-1-1,b,a,c)--
	move(4-1-1,c,a,b)
		move(4-1-1-1,c,b,a)--
	move(4-1-1-1,a,c,b)--至此循环1结束
	move(4-1,b,a,c)#2组循环开始循环2为3时
		move(4-1-1,b,c,a)
			move(4-1-1-1,b,a,c)--
		move(4-1-1-1,c,b,a)--
	move(4-1-1,a,b,c)#组循环开始循环2为2时
		move(4-1-1-1,a,c,b)--
	move(4-1-1-1,b,a,c)--
输出结果为：a-b b-c c-a a-b b-c c-a a-b b-c 
这类递归类似于波形。	
	
	
	
个人认为我这种想法应该是对的，下面是我自己突发奇想想到的一个验证我的这个想法的代码。这个代码中可以观察n的各个阶段中各个值的实际值。
def move(n, a, b, c):
    print(n,a, b, c)
    if n == 1:
        return print(a, '-->', c)
    move(n-1,a,c,b)
    move(1,a,b,c)
这个代码可以在任意步骤显示，a，b，c中的值。可以参考。



接下来就是三个递归函数的调用了。根据两个递归函数的调用来猜测一下。
def move(n, a, b, c):
	if n == 1:
		return print(a, '-->', c)
	move(n-1,a,c,b)
	move(1,a,b,c)
	move(n-1,b,a,c)
>>> move(2,'a','b','c')
a --> b
a --> c
b --> c
>>> move(3,'a','b','c')
a --> c
a --> b
c --> b
a --> c
b --> a
b --> c
a --> c
如果n的传输值为2时
move(2,a,b,c)
	move(2-1,a,c,b)--
	move(1,a,b,c)--
	move(2-1,b,a,c)--
	
如果n的传输值为3时
move(3,a,b,c)
	move(3-1,a,c,b)
		move(3-1-1,a,b,c)--
	move(1,a,c,b)--
	move(3-1-1,c,a,b)--
move(1,a,b,c)--
	move(3-1,b,a,c)
		move(3-1-1,b,c,a)--
	move(1,b,a,c)--
	move(3-1-1,a,b,c)--
详细说一下这个吧：根据之前所说的，
1.首先带入(3,a,b,c)进入递归调用，先走第一个小循环move(n-1,a,c,b)，此时n=3。
小循环中走n=3-1条件不满足，继续走小小循环n=3-1-1 return，得出结果，退出当前小小循环。
用当前小循环中的值走(1,a,b,c)输出一个值，然后用当前的n=2走小循环中的move(n-1,b,a,c)。走完之后。第一个小循环整体走完。
2.然后在整体递归函数中走move(1,a,b,c)。
3.然后开始move(n-1,b,a,c)的递归调用，同1类似。

move(4,a,b,c)
	move(4-1,a,c,b)
		move(4-1-1,a,b,c)
			move(4-1-1-1,a,c,b)--
		move(1,a,b,c)--
		move(4-1-1-1,b,a,c)--
	move(1,a,c,b)--
	move(4-1-1,c,a,b)
		move(4-1-1-1,c,b,a)--
	move(1,c,a,b)--
	move(4-1-1-1,a,c,b)--
move(1,a,b,c)--
	move(4-1,b,a,c)
		move(4-1-1,b,c,a)
			move(4-1-1-1,b,a,c)--
		move(1,b,c,a)--
		move(4-1-1-1,c,b,a)--
	move(1,b,a,c)--
	move(4-1-1,a,b,c)
		move(4-1-1-1,a,c,b)--
	move(1,a,b,c)--
	move(4-1-1-1,b,a,c)--

以上是n=4时汉诺塔的具体执行步骤。我自己能写明白。讲就算了。大家自行理解吧。

写在最后，可能我的语言表述并不是特别好，但是步骤写的很清楚了。每一次的递归，递归调用递归，递归调用常函数。常函数调递归。以及各个阶段值的变换。

因为我也才接触 python 没多久。都是自己在摸索。各位如有问题请及时联系我。我再进行相应的修改。