递归是否意味着分而治之

Question

所有递归问题背后的原理是分而治之吗？例如：查找阶乘，二叉搜索...

而且，分而治之范式是如何工作的？，为什么通过递归更容易找到阶乘？

Answer 1

递归是否意味着分而治之？

不。递归意味着归纳：将问题移动到较小的范围，直到它可以解决（基本条件），然后一直应用增量更改。

分而治之意味着将问题分成两个（或更多）较小的问题，这些问题将被递归解决。

为什么通过递归更容易找到阶乘？

这并不"容易"。有些人会争辩说，更直观的只是直觉不是数学:)中可以正确定义的东西对我来说，以迭代方式（while 循环）求解阶乘更直观。

由于没有代码示例就没有完整的答案，因此以下是递归和迭代实现（Python）中的阶乘：

def fact(n):
    if n == 0:
        return 1
    else: 
        return n * fact(n-1)
def fact_iter(n):
    res = 1;
    while n > 0:
        res *= n
        n -= 1
    return res