哪里有国内网站建设公司,做国外单的网站叫什么,青岛网站做网站多少钱,网站统计分析我们先说#xff0c;在一个函数中#xff0c;调用另一个函数。
首先#xff0c;要意识到#xff0c;函数中的代码和平常所写代码一样#xff0c;也都是要执行完的#xff0c;只有执行完代码#xff0c;或者遇到return#xff0c;才会停止。
那么#xff0c;我们在函…我们先说在一个函数中调用另一个函数。
首先要意识到函数中的代码和平常所写代码一样也都是要执行完的只有执行完代码或者遇到return才会停止。
那么我们在函数中调用函数执行完了就会重新回到本函数中继续向下执行直到结束。
在执行其它函数时本函数相当于中断了不执行了。那我们重新回来的时候要从刚才暂停的地方开始继续执行这期间所有现场信息都要原封不动就相当于时间暂停了一样什么都不能改变这样才能做到程序的准确。
所以通常在执行另一个函数之前电脑会将现场信息压入一个系统栈为被调用的函数分配存储区然后开始执行被调函数。执行完毕后保存计算结果释放被调函数的空间按照被调函数里保存的返回地址返回到原函数。
那什么是递归函数呢
就是多个函数嵌套调用。不同的是这些函数是同一个函数只是参数可能不同甚至参数也一样只是存储空间不同。
每一层递归所需信息构成一个栈每一块内存储着所有实在参数所有局部变量上一层的返回地址等等一切现场信息。每执行完就弹出。
递归函数有着广泛应用主要适合可以把自身分化成一样的子问题的问题。比如汉诺塔。 汉诺塔汉诺塔又称河内塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定在小圆盘上不能放大圆盘在三根柱子之间一次只能移动一个圆盘。
思路函数n,a,b,c)含义是把n个盘子从a柱子搬到c柱子的方法
一个盘子直接搬过去。
多个盘子我们把n-1个盘子都移动到另一个柱子上把最大的搬过去然后把剩下的搬过去。 def hanoi(n, a, b, c):if n 1:print(a, --, c)else:hanoi(n - 1, a, c, b)print(a, --, c)hanoi(n - 1, b, a, c)
# 调用
hanoi(3, A, B, C)
结果
A -- C
A -- B
C -- B
A -- C
B -- A
B -- C
A -- C 我们的栈
第一次
我们把hanoi(3, A, B, C)存了起来调用了hanoi(3-1, A, C, B),现在栈里压入了3, A, B, C还有函数执行到的位置等现场信息。然后执行hanoi(3-1, A, C, B)发现要调用hanoi(3-1-1, A, B, C)我们又把3-1, A, C, B等信息压入了栈现在栈是这样的
栈头
2, A, C, B
3, A, B, C
栈尾 然后执行hanoi(3-1-1, A, B, C)发现n1了打印了第一条A -- C然后释放掉了hanoi(3-1-1, A, B, C)的空间并通过记录的返址回到了hanoi(3-1, A, C, B)然后执行打印语句A -- B然后发现要调用hanoi(3-1-1, C, A, B)此时栈又成了
2, A, C, B 3, A, B, C
调用hanoi(1, A, C, B)发现可以直接打印C -- B。
然后我们又回到了2, A, C, B这里。发现整个函数执行完了那就弹出吧。这时栈是这样的
3, A, B, C
只有这一个。
我们继续执行这个函数的代码发现
def hanoi(n, a, b, c): if n 1: print(a, --, c) else: hanoi(n - 1, a, c, b)//执行到了这里 print(a, --, c) hanoi(n - 1, b, a, c) 那我们就继续执行发现要打印A -- C
然后继续发现要调用 hanoi(n - 1, b, a, c)那我们继续把现场信息压栈继续执行就好了。 递归就是把大问题分解成小问题进而求解。
具体执行就是通过系统的栈来实现返回原函数的功能。 多色汉诺塔问题 奇数号圆盘着蓝色偶数号圆盘着红色如图所示。现要求将塔座A 上的这一叠圆盘移到塔座B 上并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则
规则(1)每次只能移动1 个圆盘 规则(2)任何时刻都不允许将较大的圆盘压在较小的圆盘之上 规则(3)任何时刻都不允许将同色圆盘叠在一起
其实双色的汉诺塔就是和无色的汉诺塔算法类似通过推理可知无色汉诺塔的移动规则在双色汉诺塔这里的移动规则并没有违反。
这里说明第一种就可以了Hanoin-1A,C,B;
在移动过程中塔座上的最低圆盘的编号与n-1具有相同奇偶性塔座b上的最低圆盘的编号与n-1具有不相同的奇偶性从而塔座上的最低圆盘的编号与n具有相同的奇偶性塔座上c最低圆盘的编号与n具有不同的奇偶性
所以把打印操作换成两个打印即可 总因为递归可能会有重复子问题的出现。
就算写的很好无重复子问题也会因为来回调用、返回函数而速度较慢。所以有能力的可以改为迭代或动态规划等方法。
