递归算法详解

递归的三要素

接下来利用 n n n阶乘来讲解这三个条件 任何大于等于1 的自然数 n n n阶乘表示方法： n ! = n × ( n − 1 ) ! ( n > 1 ) 0 ! = 1 ( n = 0 ) n!=n \times(n-1)! \quad (n > 1) \\ 0! = 1 \quad (n = 0) n!=n×(n−1)!(n>1)0!=1(n=0)

明确我们要写的函数的功能是实现 n n n的阶乘，定义函数如下：

由阶乘的表示方法可以看出当 n = 0 n = 0 n=0时是阶乘的最小值，此时结束继续往下计算阶乘，可以把 n = 0 n = 0 n=0当做递归的结束条件。同样，当 n = 1 n = 1 n=1时， 1 ! = 1 1! = 1 1!=1也可以作为递归的结束条件。

第三要素就是，我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。 由阶乘的表达式可以看出 n n n的阶乘与 n − 1 n -1 n−1阶乘存在的关系式为 n ! = n × ( n − 1 ) ! ( n > 1 ) n!=n \times(n-1)! \quad (n > 1) n!=n×(n−1)!(n>1)若已知 n − 1 n -1 n−1的阶乘，记为 f ( n − 1 ) f(n - 1) f(n−1)，则当前的 n n n的阶乘可以记为 f ( n ) = n × f ( n − 1 ) ( n > 1 ) f(n) = n \times f(n -1)\quad (n > 1) f(n)=n×f(n−1)(n>1) 综上递归的三个要素可以得出求 n n n阶乘的递归函数为

更多的递归案例讲解点击此处.