Python函数的递归

递归的定义

递归的定义

编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。递归函数不能定义为内联函数。

在数学上，关于递归函数的定义如下：对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。

例题：求n的阶乘

n的阶乘有两种定义方法：

• n!=1×2×3×...×(n-1)×n。
• 阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n

• 这种函数在运行过程中反复调用它本身的情况，就叫做递归。
• 
• 
• 例1：阶乘的计算

在这个例子中，计算阶乘的过程中factorial又调用了它自己，这就是递归。

def factorial(num):
    if num == 0:
        return 1
    else:
        return num * factorial(num-1)
n = eval(input("请输入一个整数: "))
print(factorial(abs(int(n))))

• 例2： 字符串反转

在这个例子中，reverse在计算新字符串的过程中，又调用了它自己reverse(s[1:]) ，这也是递归。

def reverse(s):
    if s == "":
        return s
    else:
        return reverse(s[1:]) + s[0]
str = input("请输入一个字符串: ")
print(reverse(str))

递归的注意事项

在写递归函数时需要注意三个事项：

1、明确递归终止条件；

2、给出递归终止时的处理办法；

3、提取重复的逻辑，缩小问题规模。

• 例3：使用递归，求斐波那契数列

这个题中中止的条件就是n<=1 ,

每一步调用recur_fibo的过程中，参数都比以前的小，在缩小问题的规模。

# Filename : test.py
# author by : www.runoob.com
 
def recur_fibo(n):
   """递归函数
   输出斐波那契数列"""
   if n <= 1:
       return n
   else:
       return(recur_fibo(n-1) + recur_fibo(n-2))
 
 
# 获取用户输入
nterms = int(input("您要输出几项? "))
 
# 检查输入的数字是否正确
if nterms <= 0:
   print("输入正数")
else:
   print("斐波那契数列:")
   for i in range(nterms):
       print(recur_fibo(i))

• 非递归方式求解：

我们用非递归的方式对比一下：

a=0
b=1
while b < 1000:
    print(b,end=',')#end 可以将print输出到同一行并以 ,号结尾
    a, b = b, a+b;

• 问题解决：使用递归法对整数进行因数分解。

from random import randint

def factors(num, fac=[]):
    #每次都从2开始查找因数
    for i in range(2, int(num**0.5)+1):
        #找到一个因数
        if num%i == 0:
            fac.append(i)
            #对商继续分解，重复这个过程
            factors(num//i, fac)
            #注意，这个break非常重要
            break
    else:
        #不可分解了，自身也是个因数
        fac.append(num)
facs = []
n = randint(2, 10**8)
factors(n, facs)
result = '*'.join(map(str, facs))
if n==eval(result):
    print(n, '= '+result)