“Python函数的递归”的版本间的差异
来自CloudWiki
(未显示同一用户的5个中间版本) | |||
第1行: | 第1行: | ||
− | * | + | ==递归的定义== |
+ | ===递归的定义=== | ||
+ | |||
+ | 编程语言中,函数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 | ||
+ | |||
+ | *这种函数在运行过程中反复调用它本身的情况,就叫做递归。 | ||
+ | *[[文件:p5-3.png|500px]] | ||
*[[文件:p4-7.png]] | *[[文件:p4-7.png]] | ||
+ | *例1:阶乘的计算 | ||
+ | |||
+ | 在这个例子中,计算阶乘的过程中factorial又调用了它自己,这就是递归。 | ||
+ | |||
+ | <nowiki>def factorial(num): | ||
+ | if num == 0: | ||
+ | return 1 | ||
+ | else: | ||
+ | return num * factorial(num-1) | ||
+ | n = eval(input("请输入一个整数: ")) | ||
+ | print(factorial(abs(int(n))))</nowiki> | ||
+ | *例2: 字符串反转 | ||
+ | |||
+ | 在这个例子中,reverse在计算新字符串的过程中,又调用了它自己reverse(s[1:]) ,这也是递归。 | ||
+ | |||
+ | <nowiki>def reverse(s): | ||
+ | if s == "": | ||
+ | return s | ||
+ | else: | ||
+ | return reverse(s[1:]) + s[0] | ||
+ | str = input("请输入一个字符串: ") | ||
+ | print(reverse(str))</nowiki> | ||
+ | |||
+ | |||
+ | ==递归的注意事项== | ||
+ | 在写递归函数时需要注意三个事项: | ||
+ | |||
+ | 1、明确递归终止条件; | ||
+ | |||
+ | 2、给出递归终止时的处理办法; | ||
+ | |||
+ | 3、提取重复的逻辑,缩小问题规模。 | ||
+ | |||
+ | *例3:使用递归,求斐波那契数列 | ||
+ | |||
+ | 这个题中中止的条件就是n<=1 , | ||
+ | |||
+ | 每一步调用recur_fibo的过程中,参数都比以前的小,在缩小问题的规模。 | ||
+ | |||
+ | <nowiki># 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))</nowiki> | ||
+ | |||
+ | *非递归方式求解: | ||
+ | |||
+ | 我们用非递归的方式对比一下: | ||
+ | |||
+ | <nowiki>a=0 | ||
+ | b=1 | ||
+ | while b < 1000: | ||
+ | print(b,end=',')#end 可以将print输出到同一行并以 ,号结尾 | ||
+ | a, b = b, a+b; | ||
+ | </nowiki> | ||
*问题解决:使用递归法对整数进行因数分解。 | *问题解决:使用递归法对整数进行因数分解。 | ||
<nowiki>from random import randint | <nowiki>from random import randint | ||
第23行: | 第109行: | ||
if n==eval(result): | if n==eval(result): | ||
print(n, '= '+result)</nowiki> | print(n, '= '+result)</nowiki> | ||
− | |||
− |
2021年3月15日 (一) 03:06的最新版本
递归的定义
递归的定义
编程语言中,函数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
在这个例子中,计算阶乘的过程中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)