Python | 递归

qieangel2013 发布于2019-07-31 10:52 / 3043人阅读

摘要：那假如我们用递归来描述这种情况呢定义基本情况其它情形所以在上述求和中的定义又用到了自己本身的定义，这就构成了递归。

说起递归，我觉得其实大部分人应该是不陌生的，递归广泛存在于生活中。
比如：

The woman in this image holds an object that contains a smaller image of her holding an identical object, which in turn contains a smaller image of herself holding an identical object, and so forth.[from wikipedia]

那么递归的定义是什么呢？
在数学和计算机科学中，我们给出一个比较传统的定义是：
它们有两个特性。

一个基本特例，也称作平凡（一般）情况，它是递归终止的情形

一个已定义好的规则来使其它非基本的情形转化为基本情形

可能这个上面的定义比较枯燥，那么我们用一个经典的例子来说明一下。

Fibonacci sequence

Fib(0) = 0, 是一个基本情况
Fib(o) = 1, 是第二个基本情况
所以 Fibonacci sequence 总共有两个基本情形
对于其它情形，我们定义 Fib(n) = Fib(n-1) + Fib(n-2)

到这里，估计读者已经对递归有一个大概的印象了，那么在Python中我们怎么用递归来实现某些特定的功能呢？

我首先用一些简单的例子来进行说明。

例1.

假如你要求序列数列 1, 2, 3, 4, ..., n 的和。比如对于n=4，其和是10。那假如我们用递归来描述这种情况呢？
定义:

基本情况：S(1) = 1

其它情形: S(n) = S(n-1) + n
所以在上述求和中S(n)的定义又用到了自己本身的定义，这就构成了递归。

我们用Python来实现以下上面的思路。

def Sum(n):
    if n==1:
    #对应基本情形
        return 1
    return Sum(n-1) + n#对应递归情形

>>> Sum(4)
10
>>> Sum(10)
55
>>> Sum(100)
5050

代码如上，可以看到，问题如果用递归来解决的话，可以与现实很好的结合，因为现实中有很多问题也是递归定义的。
此外，使用递归编程也比较简单。

例2.

经典的求阶乘

定义 F(n) 为阶乘函数。

基本情形: F(0) = 1, F(1) = 1

其它情形: F(n) = F(n-1) * n

实现:

def F(n):
    if n==0 or n==1:
    #对应基本情形
        return 1
    return F(n-1)*n#对应递归情形

>>> F(4)
24
>>> F(10)
3628800

例3.

求 斐波那契数列

定义Fib(n) 为斐波那契数列

基本情形:

Fib(0) = 1, Fib(1) = 1

其它情形:

Fib(n) = Fib(n-1)+Fib(n-2)

实现:

def Fib(n):
    if n==0 or n==1:
        return 1
    return Fib(n-1)+Fib(n-2)

>>> Fib(10)
89
>>> Fib(8)
34
>>>

除此以外，接下来的几道题也可以用递归求解，虽然可能在有些问题上，递归并不是最合适的工具，可以使用迭代得到比递归更为高效的算法。

例4.

计算s=a+aa+aaa+aaaa+aa...a，其中 a是一个数字。
其中，a 以及 n 由用户输入，但是我们在这里就直接给定了。

定义：
函数 SSS(a, n) 的值为上述所求值

基本情形：

SSS(a, 1) = a

其它情形:
SSS(a, n) = SSS(a, n-1) + a...a(共n项)

def SSS(a, n):

    #这里我说明一下，直接用input函数得到的就是字符串，除非你已经做了转换
    #所以,我们设定a、n都是字符串
    n = int(n)#转换
    if n == 1:
        return int(a)
    return SSS(a, n-1) + int(a * n)#请思考这里a*n

>>> SSS("2", "5")
24690
>>> SSS("2", "1")
2
>>> SSS("2", "2")
24
>>>

例5.

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。比如排列[1,4,3,2]中，4在3前面，但4>3，则4和3逆序，同理，4和2逆序，3和2逆序，共有3对逆序，因此这组排列的逆序数为3。现在请你设计一个程序，判断用户输入的数组的逆序数。

定义：
OP(seq, n)为序列seq中前n项的逆序数

基本情形:
OP(seq[1...n], 1) = 0，对于只有一个元素的集合，逆序数必然只有0

其它情形:
OP(seq[1...n], n) = OP(seq[1...n, n-1] + F(n)，其中，F(n)是n关于seq[1...n-1]的逆序数.

实现:

def OP(seq, n):
    if n == 1:
        return 0
    #不为0
    Fn = 0
    for i in range(0, n-1):
        if seq[n-1] < seq[i]:
            Fn+=1
    return OP(seq, n-1)+Fn

>>> s = [5, 4, 3, 2, 1]
>>> s
[5, 4, 3, 2, 1]
>>> OP(s, len(s))
10
>>>

例6.

输入某年某月某日，判断这一天是这一年的第几天？

假如我们要用递归实现这样的程序，该怎么考虑呢？

首先，我们得定义出我们的递归函数，它有三个变量，年，月，日。

定义:WhichDay(year, month, day)

基本情况: WhichDay(year, month, day) 当month = 1时，可以看出，此时该函数的值为 day

其它情形:
WhichDay(year, month, day) = WhichDay(year, month-1, F(month-1))+day

请注意,我在递归式子中使用的F(month-1), 这个代表(month-1)这一月的总天数。

实现:

F = { 1:31, 2: 28, 3:31, 4:30, 5:31, 6:30, 7:31, 8:31, 9:30, 10: 31, 11: 30, 12: 31}
def WhichDay(year, month, day):
    if month == 1:
        return day
    flag = 0#二月是否闰年标志
    if month == 3:
        #二月特殊处理
        #这里month等于3请读者思考
        if (year % 4 == 0 and year % 100!=0) or year % 400 == 0:
            flag = 1#判断闰年
    return WhichDay(year, month-1, F[month-1]+flag)+day

>>> WhichDay(2016, 2, 1)
32
>>> WhichDay(2016, 11, 8)
313
>>> WhichDay(2016, 12, 31)
366
>>>

虽然上面的问题并不是很适合使用递归来实现，但是我主要是想跟大家分享一个递归解决问题中的思路，以及递归是一个很强大的工具，但是同时会产生很严重的效率问题。关于这一点，可以查看递归优化，可以很大程度上改善递归的效率。

希望读者看完这篇教程，可以有所收获，谢谢。

云服务器 GPU云服务器 python递归错误 python递归例子 python递归调用 python实现递归

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44235.html

处理python递归函数及递归算法频次受限制难题

　　本文关键阐述了处理python递归函数及递归算法频次受限制难题，具有非常好的实用价值，希望能帮助到大家。如有误或者未考虑到真正的地区，望鼎力相助　　递归函数及递归算法频次受限制　　一个函数在外部启用自身，那么这样的函数是递归函数。递归算法要反复应用自身，每递归算法一回，越近最后的值。如果一个难题需要由很多类似小问题处理，可以选择应用递归函数。伴随着递归算法的深层次，难题经营规模对比之前都应该所...

89542767 2022-12-29 14:58 评论0 收藏0
Python开启尾递归优化!

摘要：尾递归优化一般递归与尾递归一般递归执行可以看到一般递归每一级递归都产生了新的局部变量必须创建新的调用栈随着递归深度的增加创建的栈越来越多造成爆栈尾递归尾递归基于函数的尾调用每一级调用直接返回递归函数更新调用栈没有新局部变量的产生类似迭代的 Python尾递归优化一般递归与尾递归一般递归: def normal_recursion(n): if n == 1: ...

junnplus 2019-07-31 10:54 评论0 收藏0
小李飞刀：python你慢点飞，我的脑子还在后面追

摘要：默认参数设置默认参数时，有几点要注意一是必选参数在前，默认参数在后，否则的解释器会报错二是如何设置默认参数。注意此处，获得的其实是的拷贝，函数内对的改变不会影响到。使用递归函数需要注意防止栈溢出。总是在最前面的叨逼叨最近总是在想成长这两个很常常被提起的事情，这对于一个已经25岁的半中年而言，已经是一个不太能高频提起的词。但是，最近一些事情吧，总让我觉得我的生长期似乎比正常人来的晚了...

kevin 2019-07-30 18:40 评论0 收藏0
Python笔记

摘要：针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的，没有循环语句的编程语言只能通过尾递归实现循环。标准的解释器没有针对尾递归做优化，任何递归函数都存在栈溢出的问题。 python 头部： #!/usr/bin/env python # -*- coding: utf-8 -*- 函数的参数 Python的函数具有非常灵活的参数形态，既可以实现简单的调用，又可以传入...

yuxue 2019-07-31 10:07 评论0 收藏0
【数据科学系统学习】Python # 编程基础[一]

摘要：在定义函数时给定的名称称作形参，在调用函数时你所提供给函数的值称作实参。调用函数要调用一个函数，需要知道函数的名称和参数。默认参数值可以有效帮助解决这一情况。是默认参数定义默认参数要牢记一点默认参数必须指向不变对象。关于数据科学在做什么，我们已经在前两篇文章中进行了总结，即专题概述和描述性统计分析。要进行数据科学的探索，需要一个好工具，就是Python。从本篇开始，将总结学习Pyth...

luckyyulin 2019-07-30 17:21 评论0 收藏0