【Python】小甲鱼课后习题第22讲、23讲、24讲--函数(下)

2021/9/19 17:04:55

本文主要是介绍【Python】小甲鱼课后习题第22讲、23讲、24讲--函数(下),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

问答题


0. 递归在编程上的形式是如何表现的呢?

答:在编程上,递归表现为函数调用本身这么一个行为。

举个例子(递归求阶乘):

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

number = int(input('请输入一个整数:'))
result = factorial(number)

print("%d的阶乘是:%d" % (number, result))

1*. 递归必须满足哪两个基本条件?

答:函数调用自身和设置了正确的返回条件。

2. 思考一下,按照递归的特性,在编程中有没有不得不使用递归的情况?

答:例如汉诺塔,目录索引(因为你永远不知道这个目录里边是否还有目录),快速排序(二十世纪十大算法之一),树结构的定义等,如果使用递归,会事半功倍,否则会导致程序无法实现或相当难以理解。

3. 用递归去计算阶乘问题或斐波那契数列是很糟糕的算法,你知道为什么吗?

答:递归的实现可以是函数自个儿调用自个儿,每次函数的调用都需要进行压栈、弹栈、保存和恢复寄存器的栈操作,所以在这上边是非常消耗时间和空间的。

另外,如果递归一旦忘记了返回,或者错误的设置了返回条件,那么执行这样的递归代码就会变成一个无底洞:只进不出!所以在写递归代码的时候,一定不要忘记编写递归出口。

4. 请聊一聊递归的优缺点。

答:优点:

1)递归的基本思想是把规模大的问题转变成规模小的问题组合,从而简化问题的解决难度(例如汉诺塔游戏)。

2)有些问题使用递归使得代码简洁易懂(例如你可以很容易的写出前中后序的二叉树遍历的递归算法,但如果要写出相应的非递归算法就不是初学者可以做到的了。)

缺点:

1)由于递归的原理是函数调用自个儿,所以一旦大量的调用函数本身空间和时间消耗是“奢侈的”。

2)初学者很容易错误的设置了返回条件,导致递归代码无休止调用,最终栈溢出,程序崩溃。


动动手


0. 使用递归编写一个 power() 函数模拟内建函数 pow(),即 power(x, y) 为计算并返回 x 的 y 次幂的值。

答:代码如下:

def power(x, y):
    if y:
        return x * power(x, y-1)
    else:
        return 1
    
print(power(2, 3))

1. 使用递归编写一个函数,利用欧几里得算法求最大公约数,例如 gcd(x, y) 返回值为参数 x 和参数 y 的最大公约数。

答:代码如下:

def gcd(x,y):
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)

print(gcd(2,5))

0. 使用递归编写一个十进制转换为二进制的函数(要求采用“除2取余”的方式,结果与调用bin()一样返回字符串形式)。

答:代码如下:

def Dec2Bin(dec):
    result = ''
    
    if dec:
        result = Dec2Bin(dec//2)
        return result + str(dec%2)
    else:
        return result

print(Dec2Bin(62))

1. 写一个函数get_digits(n),将参数n分解出每个位的数字并按顺序存放到列表中。举例:get_digits(12345) ==> [1, 2, 3, 4, 5]

答:代码如下:

result = []
def get_digits(n):
        if n > 0:
                result.insert(0, n%10)
                get_digits(n//10)

get_digits(12345)
print(result)

3. 使用递归编程求解以下问题:

有5个人坐在一起,问第五个人多少岁?他说比第4个人大2岁。问第4个人岁数,他说比第3个人大2岁。问第三个人,又说比第2人大两岁。问第2个人,说比第一个人大两岁。最后问第一个人,他说是10岁。请问第五个人多大?

答:解题思路:利用递归的方法,递归分为回推和递推两个阶段。要想知道第五个人岁数,需知道第四人的岁数,依次类推,推到第一人(10岁),再往回推。

代码如下:

def age(n):
    if n == 1:
        return 10
    else:
        return age(n-1) + 2
        
print('哈哈,我知道了,第五个人的年龄是 %d 岁,啵啵脆!' % age(5))



这篇关于【Python】小甲鱼课后习题第22讲、23讲、24讲--函数(下)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程