文章

python 递归(Recursion)

文章目录

递归

是函数式编程中一个非常重要的概念。

递归的基本部分是自引用 - 调用自己的函数。它被用来解决可以被分解成相同类型的更容易的子问题的问题。
一个递归实现的函数的典型例子是阶乘函数,N的阶乘写作N!表示小于等于N的所有正整数的乘积。

例如,5! (5的阶乘)是 5 * 4 * 3 * 2 * 1(120)。可以这样拆解然后用递归实现, 5! = 5 * 4!,4! = 4 * 3!,3! = 3 * 2! 等等。一般来说,n! = n * (n-1)!,然而,1! = 1 被称为基准情形(base case),因为它可以被直接计算,而不用执行更多的阶乘因子。

以下是阶乘函数的递归实现。

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

print(factorial(5))

基准情形充当递归的退出条件。

递归函数可以是无限的,就像无限循环一样。当你忘记设置基准情形(base case)时,经常发生这种情况。
以下是阶乘函数的错误版本。它没有基准情形(base case),所以它运行,直到解释器内存不足而崩溃。

def factorial(x):
  return x * factorial(x-1)

print(factorial(5))
结果:

RuntimeError: maximum recursion depth exceeded

递归也可以是间接的。一个函数可以调用第二个函数,第二个函数再调用第一个函数,依此类推。这可以发生在任何数量的函数上。
例如:

def is_even(x):
  if x == 0:
    return True
  else:
    return is_odd(x-1)

def is_odd(x):
  return not is_even(x)


print(is_odd(17))
print(is_even(23))
    结果:
    True
    False
原文来自:python 递归(Recursion),尊重自己,尊重每一个人;转发请注明来源!
0 0

发表评论