浅谈python中的递归

2018-06-23 13:27:44来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

python 浅谈 递归函数
最近在自学一些python,找了些资料。自己慢慢研究到了递归函数这一章,碰到个很经典的例子。汉诺塔的移动。一开始尝试自己写的时候发现,这东西怎么可能写的出来。但是看到别人写出来以后发现,这东西真的能写出来。
本着借鉴的目的想去分析一下别人写的东西。觉得很有意思想给大家分享一下,如果有误请大家指正首先大家可以先自己想想如何能写出来。
先说一下:所谓的递归,我认为就是不断重复调用。直到return 出当前的递归循环。在我拆分的过程中,大家不妨先自己想一下结果,然后看一下我执行出来的结果,是否和各位所想的一样呢。
本文仅代表自己观点,如有错误大家指出。

	--------------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没多久。都是自己在摸索。各位如有问题请及时联系我。我再进行相应的修改。

  

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:python中sorted方法和列表的sort方法使用详解

下一篇:Python源码剖析之准备工作