Python函数递归

今天继续给大家介绍Python相关知识，本文主要内容是Python函数递归

一、函数递归概述

在一个编程语言引入函数后，就产生了利用函数递归解决问题的方法。函数递归，在本质上来说，就是在某个函数中，调用了该函数自身。利用函数递归，类似于数学中的数学归纳法。我们需要做的是找到某问题计算过程中上一步和下一步之间的关系，就自然而然可以编写出函数递归的代码。
函数的递归存在两个关键的特征：链条和基例。所谓链条，就是计算过程中存在的递归链条，而基例，则是在函数递归过程中需要用到的一个或者多个不需要递归，而是能够直接得到结果的例子。
下面，我们就用两个实例，来展示以下函数递归的魅力。

二、函数递归实例一：斐波那契数列问题

斐波那契数列问题，是数学中数列的经典问题。斐波那契数列假设在第一年有1对小兔子，小兔子长大需要一年的时间称为大兔子，大兔子每年可以生一对小兔子。假设兔子不死亡，那么N年后有多少对兔子。
很显然，对于这个问题，第一年有1对，第二年也有1对，从第三年往后，每年的兔子数等于去年的兔子数加上今年新出生的兔子数，而今年新出生的兔子数又等于今年的大兔子数，今年的大兔子数又等于前年所有的兔子数。因此，每年的兔子数等于去年的兔子数，加上前年的兔子数。
根据上述分析，我们利用代码递归，编写代码如下所示：

def f(n):
    if n==1:
        return 1
    if n==2:
        return 1
    return f(n-1)+f(n-2)
for i in range(1,10):
    print(f(i))
1
2
3
4
5
6
7
8

上述代码执行结果如下所示：

三、函数递归示例二：汉诺塔问题

汉诺塔问题，也是函数递归中的经典问题。但是对于编程小白而言，这个问题存在一定的难度，主要就是理解函数递归中的链条，即每一步操作之间的关系。
汉诺塔问题说有三根柱子，第一根柱子上摞着一摞碟子，并且从下到上碟子不断减小。现在我们要把碟子从第一根柱子移到第三根柱子，要求每次只能移动一个碟子，并且在移动过程中，每根柱子上的碟子必须从下到上碟子不断减小。
分析这个问题，我们可以先从碟子数为3开始，发现我们当碟子数为3时，我们可以完成。如果扩展到碟子数为n，假设我们可以完成n-1这样的操作，那么我们完全可以先把前n-1个碟子移动到中间的柱子上，然后再把第n个碟子移动到最后的柱子上，最后再把前面的n-1个碟子移动到最后的柱子上。
基于此分析，我们可以编写以下代码：

def last()
def hanno(n,start,medium,end):
    if n==3:
        print("1:{}->{}".format(start,end))
        print("2:{}->{}".format(start,medium))
        print("1:{}->{}".format(end,medium))
        print("3:{}->{}".format(start,end))
        print("1:{}->{}".format(medium,start))
        print("2:{}->{}".format(medium,end))
        print("1:{}->{}".format(start,end))
        return
    hanno(n-1,start,end,medium)
    print("{}:{}->{}".format(n,start,end))
    hanno(n-1,medium,start,end)
hanno(4,'A','B','C')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

上述代码执行过程如下所示：

从上图中可以看出，我们能够成功的把碟子从第一根柱子移动到第n根柱子。
原创不易，转载请说明出处：https://blog.csdn.net/weixin_40228200