• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【python】递归听了N次也没印象,读完这篇你就懂了

开发技术 开发技术 2周前 (02-21) 8次浏览

听到递归总觉得挺高大上的,为什么呢?因为对其陌生,那么今天就来一文记住递归到底是个啥。

不过先别急,一起来看一个问题:求10的阶乘(10!)。

求x的阶乘,其实就是从1开始依次乘到x。那么10的阶乘就是 1*2*3*4*5*6*7*8*9*10

一、非递归方式求阶乘

假如,我们在没接触过递归的情况下,如何去解决这样的问题呢?

最简单粗暴的方式 直接print(1*2*3*4*5*6*7*8*9*10)出结果就行了,结果是3628800

但是这种方式显然不是我们想要的,那么可以试试用for循环的方式来解决。

def factorial(n):
    """
    n 就是要求的阶乘的数字
    """
    result = n
    for i in range(1, n):
        result *= i

    return result

if __name__ == '__main__':
    print(factorial(10))

二、递归方式求阶乘

1. 什么是递归?

相信大家一定都听过这么一个故事:

从前有座山,山里有做庙,庙里有个老和尚在讲故事,讲的什么呢?
  从前有座山,山里有做庙,庙里有个老和尚在讲故事,讲的什么呢?
    从前有座山,山里有做庙,庙里有个老和尚在讲故事,讲的什么呢?
      ...

其实这种就是递归,说白了,就是自己去引用自己。
那么,递归用在函数中,就可以是这样的:

def factorial():
    factorial() 

if __name__ == '__main__':
    factorial()

在调用函数factorial的时候 在函数中又继续调用factorial,跟上面的故事一样,就可以无穷无尽的递归下去,
直到讲故事的老和尚累晕,以及电脑的内存溢出宕机。

但是,重要的一点,递归只是解决问题的一种方式而已,比如上面的求阶乘,我用for循环一样解决。

2. 递归解决阶乘

如果要用递归解决上面的阶乘问题,可以再进一步了解下递归的整体思想。

递归的整体思想就是,将一个大问题分解成一个个的小问题,直到问题没有办法再继续分解,于是,再去解决问题。
那么,递归式函数就要满足2个条件:

  • 基线条件:问题可以被分解为的最小问题,当满足基线条件时候,递归不再进行
  • 递归条件:继续分解问题
    可以用这个思想来尝试用递归的方式解决阶乘的问题。
10! = 10 * 9!   # 10的阶乘其实可以看做是10 * 9的阶乘
9! = 9 * 8!     # 9的阶乘可以看做是9 * 8的阶乘
8! = 8 * 7!
...
2! = 2 * 1!
1! = 1

可以看到,最后分解到1的时候就不可再继续分解了,那么1就是基线条件了。

def factorial(n):
    # 基线条件,当满足时,则不再递归
    if n == 1:
        return 1

    # 递归条件,当n不等于1时,继续递归
    return n * factorial(n - 1)

if __name__ == '__main__':
    print(factorial(10))

三、总结

  • 递归:只是解决问题的一种方式,不一定非要用
  • 递归式函数:就是函数自己调用自己
  • 递归的2个条件:基线条件(满足则不再递归)、递归条件(满足则基线递归)
  • 递归跟循环类似:基本可以互相替代
  • 循环编写起来比较容易,阅读起来比较难。递归编写起来比较难,但是阅读容易

程序员灯塔
转载请注明原文链接:【python】递归听了N次也没印象,读完这篇你就懂了
喜欢 (0)