如何编写递归函数

Question

递归函数怎么写？你能给我解释一下函数中递归的原理吗，最好是一些像阶乘或斐波那契数列这样的例子？

Answer 1

如果我理解正确，第二个和可以在C#中计算如下。

public static Sum(int n)
{
    if ( n == 0 ) // end of recursion, so-called "base case"
    {
        return 0;
    }
    else          // recursion
    {
        return n * n + Sum(n-1);
    }
}

Answer 2

基本模式是

function(arg) 
    if baseCase 
        return fixedValue
    else
        modify arg
        return function(newArg)

所以权力的例子

function int pow(int num) {
    if (num == 0 ) return 1;
    else return num ^ 2 + pow(--num);
}

Answer 3

例如 Python 中的这种方式：

def f( num ):
    if num == 0:
        return 1

    return num * f( num-1 )

这是阶乘的例子。

通常，您 return 不仅是一些值，而且甚至调用函数本身，因此它会运行再次使用另一个参数。最终它会停止沉浸，当你 return 只有一个值而没有进一步调用函数时（这里我们 return 1 作为停止器）。

对于num=3，它将是这样的：

f(3)
  |
  return 3 * f(2)
               |
               return 2 * f(1)
                            |
                            return 1 * f(0)
                                         |
                                         return 1

最后倒退，所以：

这就是我们的阶乘 :-)

如何编写递归函数

How to write recursive functions

recursion

function