【Pyhon 022讲心得体会】【递归求最大公约数】

heidern0612

写的内容都是自我思考的过程，难免有疏漏和错误的地方，欢迎广大鱼油给予指正！


1、递归

终于老师讲到了递归，老师也说了，这是新手进阶的第一个难点，递归递归，归去来兮。

有归去了，还得有回来的条件，不然就像老师说的，掉进马里亚纳海沟里，见不到影了。

这也是我理解的第一个难点，总感觉就在门外面晃悠，总是不得门而入，总是感觉临门差了一脚。

老师讲的能理解，但是具体到自己写，自己算，就懵逼了。



A、递归是神马？

是这个：



也是这个：



大多数情况下，我们见到的是一个函数调用其他函数。除此之外，函数还可以自我调用，这种类型的函数被称为递归函数



B、递归（Recursion），在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。

在使用递归时，需要注意以下几点：

1、递归就是在过程或函数里调用自身

2、必须有一个明确的递归结束条件，称为递归出口。

注意： 切勿忘记递归出口，避免函数无限调用。


C、典型的算法：

大多数学过数学、计算机科学或者读过编程相关书籍的人，想必都会遇到阶乘：

n! = 1 × 2 × 3 × … × n

也可以用递归方式定义：

n! = (n-1)! × n                （我高中数学学的并不好，遇到这个会懵逼！）

其中，n >= 1，并且 0! = 1。

由于简单、清晰，因此其常被用作递归的示例。



D、
迭代实现:

def factorial(n):
    result = 1
    for i in range(2, n+1):
        result *= i
    return result

print(factorial(1))
print(factorial(5))
print(factorial(10))

递归实现:

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



print(factorial(1))
print(factorial(5))
print(factorial(10))

为了明确递归步骤，对 5! 进行过程分解：

factorial(5)                        # 第 1 次调用使用 5
5 * factorial(4)                    # 第 2 次调用使用 4
5 * (4 * factorial(3))              # 第 3 次调用使用 3
5 * (4 * (3 * factorial(2)))        # 第 4 次调用使用 2
5 * (4 * (3 * (2 * factorial(1))))  # 第 5 次调用使用 1
5 * (4 * (3 * (2 * 1)))             # 从第 5 次调用返回
5 * (4 * (3 * 2))                   # 从第 4 次调用返回
5 * (4 * 6)                         # 从第 3次调用返回
5 * 24                              # 从第 2 次调用返回
120                                 # 从第 1 次调用返回



E、递归的优缺点:

从“编程之美”的角度来看，引用一句伟大的计算机编程名言：

To iterate is human,to recurse divine.
迭代者为人，递归者为神。                – L. Peter Deutsch



优点：

递归使代码看起来更加整洁、优雅
可以用递归将复杂任务分解成更简单的子问题
使用递归比使用一些嵌套迭代更容易



缺点:

递归的逻辑很难调试、跟进
递归调用的代价高昂（效率低），因为占用了大量的内存和时间。



我自己研究递归的时候，经常陷入了死循环找不回来，后来发现从小往大了推，比较好推，也就是先考虑递归跳出的那个条件，从最基层，一层层由里往外推，这样比较好理解。

不知道小伙伴们有没有跟我一样思考的。



2、动动手解析：

A、求次幂应该比较好理解，做过多少次了，转换下思路就有了。

def power(x, y):                                #定义一个函数，两个变量。（X为基数，Y为次幂。）
    if y:                                                #如果Y不为零的情况下
        return x * power(x, y-1)                #下面给出两个变量的值，先考虑Y为1的情况，返回1；Y为2的情况下，返回2*（2*1）,；Y为3的情况下，返回2*（2*2）=8.
    else:
        return 1                                        #Y为零的话返回值1给函数（任何数的0次幂都是1.）
    
print(power(2, 3))

B、第二个动动手需要首先理解什么叫最大公约数，然后百度下欧几里得算法，前面如果认真做过课后作业的同学，理解了欧几里得算法， 这个题就简单了。

这里还是借用个我的老图算最大公约数：



简单说就是两者一起除，商的乘积。




欧几里得算法【这里借用论坛大神的解释（原贴地址）】：

a除b 商c余d ---〉gcd(a,b) = 第二次循环变成 gcd( b , d ) 。当除数y不为0时候，再次调用gcd（），为0时，返回被除数x 。

若x < y，比如gcd（ 4 , 5 ） 。 4除5，商0余4，再次调用 变成gcd( 5 , 4)，变相的把两个变量x、y换位了。

都理解了，其实这个题也就那么回事，需要思考的是老师算法实现过程而已。

def gcd(x, y):                                
    if y:
        return gcd(y, x%y)                
    else:
        return x                                
print(gcd(4, 6))

TCY

def power(x, y, z=None):
    if z is None:
        if y:                                                #如果Y不为零的情况下
            return x * power(x, y-1)                #下面给出两个变量的值，先考虑Y为1的情况，返回1；Y为2的情况下，返回2*（2*1）,；Y为3的情况下，返回2*（2*2）=8.
        else:
            return 1                                        #Y为零的话返回值1给函数（任何数的0次幂都是1.）
    else:
         if y:
            return x * power(x, y-1) % z
        else:
            return 1
    
print(power(2, 3))

来论坛学潮汕话

TCY 发表于 2018-11-20 19:54

你这段代码为啥要加个参数z呢？

来论坛学潮汕话

其实这样的递归调用返回新手还是很难看懂，我推荐一个我在廖雪峰视频下看到的方法，瞬间就懂了。

                               
登录/注册后可看大图

来论坛学潮汕话

其实，我递归都懂了，迭代却还是不太懂

for i in range(2,n+1):
            result *= i
 return result

为啥result可以把2到n+1的值都乘起来？难道是result每乘一次i ,都return 一次result，然后再乘一次i。
例如传入的参数为3，那么result *=2，值为2。然后return result回到range中，再result *= i，也就是2 *= 3，值为6，再return其结果给函数

来论坛学潮汕话

                               
登录/注册后可看大图

咋图片就是发不出来呢？

来论坛学潮汕话

                               
登录/注册后可看大图

四点好

你这个写的很好