python :递归函数

目录

什么是递归

递归例子

1计算0到n的所有的数的和

计算阶乘

汉诺塔

斐波那契数列

什么是递归

递归函数不是python的专属，而是一种编程思想。

首先介绍一下什么是递归：

程序调用自身的编程技巧称为递归（ recursion）。递归作为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解

说简单点就是：

一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数

注意：递归函数需要一个结束条件，即（出口），递归函数不能无限调用。

递归例子

1计算0到n的所有的数的和

迭代实现

n=3
n1=0
for i in range(1,n+1):
    n1+=i
print(n1)
输出结果：
6

递归实现

def num(n):
    if n==1:
        return 1
    return n+num(n-1)
print(num(3))
输出结果;
6

其中：return 1 就是这个递归函数的出口

这个函数的思路就是：0到n的所有数的和等于0到（n-1）的所有数的和加上n，以此类推最终会到0到1的所有数的和，这时候这个问题已经无法再细分了，所以返回1.

计算阶乘

迭代实现

n=5
n1=1
for i in range(1,n+1):
    n1*=i
print(n1)
输出结果：
120

递归实现

def num(n):
    if n==1:
        return 1
    return n*num(n-1)
print(num(5))
输出结果：
120

这里的实现思路和上面的基本一致，就只是把假发变成了乘法。

汉诺塔

法国数学家 爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神 梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而 梵塔、庙宇和众生也都将同归于尽。

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

看完介绍，你可能会有些头大，这个和递归有什么关系，就算有那又怎么解决呢？、

 

其实思路很简单：如图要把金片从a移动到c可以分解为三个步骤

1先把63个金片从a移动到b

2把最后一片移动到c

3把63个金片从b移动到c

这单个步骤又可以再次进行细分，一直到细分到移动最上面一块金块。

这就满足了递归，因此我们只需要写出这三步就可以，利用递归推算出后面的步骤

实现代码：

def move(n, a, b, c):
    if(n == 1):
        print(a,"--->",c)
        return
    move(n-1, a, c, b)
    move(1, a, b, c)
    move(n-1, b, a, c)
move(4, "a", "b", "c")

除此以外我们还可以用递归来计算一下完成汉诺塔所需要的步骤：

def f(n):
    if n==0:
        return 0
    else:
        return 2*f(n-1)+1
输出结果：
18446744073709551615         

换算一下，如果一秒一步解决这个问题需要5845.42亿年，那还真是宇宙都快毁灭了。

斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

要实现斐波那契数列我们要抓住一个重点：

F(n)=F(n - 1)+F(n - 2)（n ≥ 2）

有了这个公式，就可以分别用迭代，和递归来实现了：

迭代

n=10
n1=1
n2=1
n3=1
for i in range(0,n-2):
    n3=n1+n2
    n1=n2
    n2=n3

输出结果：
55

递归

def num(n):
    if (n==1 or n==2):
        return 1
    else:
        return rabbit2(n-1)+rabbit2(n-2)
print(num(10))
输出结果;
55