|
《Windows游戏编程大师技巧》（第二版）第11章(8) n--; } // end while // return the result
return(sum); } // end Factorial
看上去非常简单。如果输入0或1，则计算结果为1。若输入3，则其计算顺序如下：
sum = sum * 3 = 1 * 3 = 3
sum = sum * 2 = 3 * 2 = 6
sum = sum * 1 = 6 * 1 = 6 显然，计算结果正确无误。因为3! = 3*2*1。 以下是采用递归方法编写的程序：
int Factorial_Rec(int n)
{
// test for terminal cases
if (n==0 n==1) return(1);
else
return(n*Factorial_Rec(n-1)); } // end Factorial_Rec
这个程序并不怎么复杂。我们看看当n分别为0和1时，程序是如何运行的。在这两种情况下，第一个if语句为TRUE，就返回值1并退出程序。但当n>1时，奇妙的事情就发生了。这时，执行else语句并返回该函数调用自身（n-1）次后的值。这就是递归过程。
当前函数变量的取值仍在堆栈里保存，下次调用该函数就相当于调用一个以一组新变量为参数的函数。代码中第一个return语句在进行下一个调用前不能执行完毕，就这样一直循环下去直到执行结束语句为止。
让我们来看一看n=3时，每次迭代时变量n的实际数值。
1. 第一次调用函数Factorial_Rec(3)，
函数开始执行return语句：
return(3*Factorial_Rec(2));
2. 第二次调用函数Factorial_Rec(2)，
函数又开始执行return语句：
return(2*Factorial_Rec(1));
3. 第三次调用函数Factorial_Rec(1)，
这次函数执行结束语句并返回值1：
return(1);
现在奇妙的是，1被返回给第二次调用的函数Factorial_Rec()，如下所示：
return(2*Factorial_Rec(1)); 这也就计算出了
return(2*1); 随之这一数值便被返回给第一次调用的函数，如下所示：
return(3*Factorial_Rec(2));
这也就计算出了
return(3*2);
And presto, the function can finally return with 6—which is indeed 3! That's recursion. Now, you might ask which method is better—recursion or non-recursion? Obviously, the straightforward method is faster because there aren't any function calls or stack manipulation, but the recursive way is more elegant and better reflects the problem. This is the reason why we use recursion. Some algorithms are recursive in nature, trying to write non-recursive algorithms is tedious, and in the end they become recursive simulations that use stacks themselves! So use recursion if it's appropriate and simplifies the problem. Otherwise, use straight linear code.
随之函数最终得到返回值6即3！。这便是递归过程。这时你会问哪种方法更好一些呢——是递归法还是非递归法？很明显，直接方法执行速度要快一些，因为没有涉及到任何函数调用或堆栈操作。但递归方法更优雅，能更好地反映问题的本质。这就是我们使用递归的原因。有些算法本质上是递归的，为之编写非递归算法会非常冗长，而且最终也必须使用堆栈进行递归模拟。如果适于简化问题，就使用递归法编程；否则就使用直接方法。
| 
