面试题：JavaScript条件语句与循环结构：递归与循环的性能优化

Question

实现一个函数 `factorial` 用于计算阶乘，分别使用递归和 `for` 循环两种方式实现。然后分析这两种实现方式在计算大数（例如1000的阶乘）时可能出现的性能问题，并说明如何优化。请阐述你的优化思路及具体实现代码。

Answer 1

递归实现

def factorial_recursive(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial_recursive(n - 1)

for循环实现

def factorial_loop(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

性能问题分析

1. 递归实现：递归实现存在栈溢出风险，因为每一次递归调用都会在栈中分配空间。对于大数（如1000的阶乘），递归深度会非常大，很容易导致栈溢出。
2. for循环实现：for循环实现没有栈溢出风险，但对于非常大的数，计算结果会非常大，普通整数类型可能无法存储，会导致溢出。

优化思路及实现

1. 递归优化：可以使用尾递归优化，将递归转化为迭代形式。尾递归是指在递归函数的最后一步调用自身，这样编译器或解释器可以优化栈空间的使用。然而，Python默认不支持尾递归优化，需要手动模拟栈实现。

def factorial_tail_recursive_helper(n, acc=1):
    if n == 0 or n == 1:
        return acc
    else:
        return factorial_tail_recursive_helper(n - 1, acc * n)

def factorial_tail_recursive(n):
    return factorial_tail_recursive_helper(n)

2. 处理大数：对于计算大数阶乘，Python提供了 math 模块中的 factorial 函数，它可以处理大数。另外，也可以使用 decimal 模块来精确处理大数运算。

import decimal

def factorial_decimal(n):
    result = decimal.Decimal(1)
    for i in range(1, n + 1):
        result *= decimal.Decimal(i)
    return result

这样通过使用 decimal 模块，可以避免整数溢出问题，精确计算大数阶乘。