ex05 函数与递归

要学习的知识点

函数定义、参数与 return
阶乘的数学定义
递归终止条件
递归调用与调用栈
for 循环累乘

题目

练习 5：分别用递归和循环计算 n!。

输入一个非负整数 n（建议 n <= 900）。

参考程序：ex05.py；空白练习：lx05.py。

完整代码

以下内容与 ex05.py 一致，可对照右侧讲解阅读。

"""练习 5：分别用递归和循环计算 n!。
输入一个非负整数 n（建议 n <= 900）。

学习说明：
- 阶乘定义为 n! = n * (n-1) * ... * 1，且 0! = 1。
- factorial_recursive() 每次把问题变成更小的 n-1；先得到较小阶乘，再乘以 n。
- n 到 1 或 0 时返回 1，称为递归终止条件。
- factorial_iterative() 从 1 开始，用 for 循环依次乘上 2 到 n。
- 主程序先读取 n；负数不符合题目条件，否则分别调用两个函数对照结果。
- 递归有调用层数限制，所以题目建议 n 不要过大。
"""
def factorial_recursive(n):
    if n <= 1:
        return 1

    smaller_factorial = factorial_recursive(n - 1)
    result = n * smaller_factorial
    return result


def factorial_iterative(n):
    result = 1
    for value in range(2, n + 1):
        result = result * value
    return result


n = int(input())
if n < 0:
    print("n must be non-negative")
else:
    print("recursive:", factorial_recursive(n))
    print("iterative:", factorial_iterative(n))

进阶写法

这版与初学版解决同一道题，写法更精炼。先读代码，再看下面的简要说明。

进阶源码文件：ex05_adv.py

"""练习 5 进阶版：直接将递归调用写在乘法表达式中。"""
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)


def factorial_iterative(n):
    result = 1
    for value in range(2, n + 1):
        result *= value
    return result


n = int(input())
if n < 0:
    print("n must be non-negative")
else:
    print("recursive:", factorial_recursive(n))
    print("iterative:", factorial_iterative(n))

递归版把调用直接写进乘法：先求 factorial_recursive(n-1)，再乘 n；循环版用 *= 缩写 result = result * value。两种写法都更紧凑，但递归终止条件不能省略。

运行结果

示例输入：

程序输出：

recursive: 120
iterative: 120

逐个认识函数

下面只列出本程序实际用到的写法；先看参数如何传入，再看返回值怎样保存或输出。

函数/写法	功能与返回值	注意事项
`factorial_recursive(n)`	自定义递归函数，返回 n 的阶乘。	n<=1 时返回 1；其他情况先求较小阶乘，再乘 n。
`factorial_iterative(n)`	自定义循环函数，返回 n 的阶乘。	从 result=1 开始，依次乘上 2 到 n。
`input()`	读取一行并返回字符串。	用 int() 将输入转换成整数。
`int(text)`	把整数文本转换为整数。	本题要求非负整数。
`range(2, n + 1)`	产生 2 到 n 的整数，停止值不包含在内。	n=0 或 1 时循环不执行。
`print(...)`	输出对象；返回 None。	分别显示递归和循环的计算结果。

函数的组成

def 函数名(参数):
    函数体
    return 结果

def 定义函数。调用函数时给参数提供具体值；return 把结果交还给调用者，并结束本次函数运行。

函数	参数	返回值	作用
`factorial_recursive(n)`	非负整数 n。	整数 n!。	把 n! 化成 `n * (n-1)!`，递归地调用自己。
`factorial_iterative(n)`	非负整数 n。	整数 n!。	从 1 开始用循环逐个相乘。
`int(input())`	input 返回的数字文本。	整数。	读入并转换 n。
`print(...)`	一个或多个显示对象。	None；作用是输出，不是算出可继续使用的值。	分别显示两个版本的结果。

递归像逐层拆小问题

问 5! 是什么：5 × 4!。
问 4!：4 × 3!，不断把问题缩小。
到 1! 时返回 1；0! 也规定为 1。这是终止条件，阻止无限调用。
函数逐层返回：2×1、3×2、4×6、5×24，得到 120。

def factorial_recursive(n):
    if n <= 1:       # 终止条件
        return 1
    return n * factorial_recursive(n - 1)

每次递归都必须让问题向终止条件靠近。漏掉终止条件会不断调用，最终触发递归深度错误。

循环版本在做什么

result = 1
for value in range(2, n + 1):
    result *= value

range(2, n + 1) 产生 2 到 n，右端不包含，所以要写 n+1。result = result * value 表示把当前结果乘以 value，再保存回 result。当 n 为 0 或 1 时循环不执行，初始值 1 正好符合定义。

递归写法更贴近数学定义，循环写法通常更节省调用空间。Python 整数可以保存很大的结果，但递归有调用层数限制。

代码如何运行

先按左侧题目给出的格式输入数据；程序通过 input() 读取，并在需要时转换数据类型。
程序自上而下执行语句；遇到条件、循环或函数调用时，按照右侧算法说明更新变量和处理数据。
最后由 print() 输出计算结果。可将左侧示例输入与输出逐项对照。

先自己跟踪一组小数据，记录循环前后变量的值；这比只看最终答案更容易理解程序。

自己动手试一试

测试 n=0、n=1；递归版本还可以尝试较大的 n，观察递归深度限制。

先在 lx05.py 中独立完成，再运行参考程序比较结果。修改程序时一次只改一个条件或步骤。