递归简单说来就是调用自身的意思。

来看一个幽默的定义:

recursion \ri-'k&r-zh&n\ n : see recursion
(递归[名词]:见递归)

一、计算n的阶乘

n的阶乘定义为 n \* (n-1) \* (n-2) \* ... \* 1

使用循环实现

def factorial(n):
  result = n
  for i in range(1, n):
    result *= i #依次与1至n-1的数相乘
  return result

首先,把数字n赋值给result,然后result依次与1n-1的数相乘,最后返回结果。

阶乘的数学定义:

  • 1的阶乘是1;
  • 大于1的数n的阶乘是n乘n-1的阶乘。

使用递归实现

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

二、计算幂

python的内建函数 pow(x, n) 或者 ** 运算符可以实现幂的计算。pow(x, n)x 自乘 n-1次,例如pow(2, 3)2乘以自身两次:2 * 2 * 2 = 8

使用循环实现

def power(x, n):
  result = 1
  for i in range(n):
    result *= x
  return result

使用递归实现

  • 对于任意数字x来说,power(x, 0)1
  • 对于任何大于0的数来说,power(x, n)x乘以(x, n-1)的结果。
def power(x, n):
  if n == 0:
    return 1
  else:
    return x * power(x, n-1)