使用递归法对整数进行因数分解pta

递归法对整数进行因数分解是一种常见的算法策略，它基于这样一个事实：每个大于1的自然数要么是一个质数（只有两个正因数：1和自身），要么可以表示为两个较小数的乘积。递归过程的基本步骤是：

1. **基本情况**：如果给定的数字n是1，那么它本身就是一个因数，此时直接返回1作为结果，因为1除以1等于1。
2. **递归情况**：对于任意非素数n，尝试找到最小的一个素数p，使得p能够整除n。然后，将n除以p得到商q，接着递归地对商q进行因数分解，最后的结果就是初始的n、p以及分解后的q的因数列表。

以下是简单的Python代码示例：

def factorize(n, factors=None):
    if n == 1:  # 基本情况：1的因数只有一个，即1
        return [1]
    elif n < 2 or factors is None:  # 如果n小于2或factors未初始化，说明n是质数
        return [n]
    else:  # 递归情况
        p = find_smallest_prime_divisor(n)  # 找到n的第一个质因子
        q = n // p  # 计算剩余部分
        return [p] + factorize(q, factors=[p])  # 将p添加到已知因数中，并继续递归

def find_smallest_prime_divisor(n):
    for i in range(2, int(n**0.5)+1):  # 只需检查到√n即可
        if n % i == 0:
            return i
    return n  # 如果没找到质因子，n本身就是质数

# 示例
n = 36
print(factorize(n))  # 输出：[2, 2, 3, 3]