Question

关于C中的递归和递推？有点晕，新手多包涵

区别在于哪里？例如求N!
用递归和递推的代码都是什么？C语言中的？
请赐教？

Answer 1

我想你要说的是递归和循环（从程序执行角度，递推比较侧重逻辑推理）。递归可以看作一个逆向求解的过程，循环则可以看作一个正向求解的过程。

unsigned long
fac0(int n)
{
return (n == 0 ? 1 : n * fac0(n-1));
}

unsigned long
fac1(int n)
{
int i;
unsigned long r;

for (r = 1, i = 1; i <= n; ++i)
r *= i;

return r;
}

fac0是用递归定义的，fac1是用循环定义的。两者字面上的区别就是，递归定义的函数体里面必然要自调用（在fac0的定义里面我们调用了fac0(n-1)），相反以循环定义的函数fac1里面却没有自调用。

递归与循环更深层次的区别则在执行的过程上。在一个没有提供尾调优化的编译器上，递归的执行效率比循环低很多，也就是说当输入很大时，循环实现将比递归实现更快地给出结果。为什么会这样呢？我们看一个计算fac0(3)和fac1(3)的比较：

fac0(3) = 3 * 调用fac0(3-1)，等待fac0(2)的返回值
fac0(2) = 2 * 调用fac0(2-1)，等待fac0(1)的返回值
fac0(1) = 1 * 调用fac0(1-1)，等待fac0(0)的返回值
fac0(0) = 1 fac0(0)直接返回1
fac0(1) = 1 拿到fac(0)的返回值1，算出1*1返回1
fac0(2) = 2 拿到fac0(1)的返回值1，算出2*1返回2
fac0(3) = 6 拿到fac0(2)的返回值2，算出3*2返回6

所以你看到递归实现会有一串调用返回的过程，正是这一频繁调用返回的过程将耗去很多的时间，而且伴有等待，这一等待也是有开销的，因为一般函数的调用和返回在底层是通过调用栈（call stack）实现的，当一个函数调用另一个函数时，调用函数要先把自己的当前状态保存到调用栈，然后跳到被调用函数体里面执行，等到那里执行完后，被调用函数返回，之前的调用函数才又从调用栈恢复。所以一条函数调用链越长，意味着将有越多的中间状态被保存到调用栈，如果输入很大，比如fac0(100)，就会生成一条很长的调用链fac0(100) --> fac0(99) --> ... --> fac0(0)，而调用栈的大小一般都有一个上限，这条调用链很可能还没有到达fac0(0)开始返回，中间需要保存的状态就已经超出这个上限了，于是就产生栈溢出（stack overflow）的错误。所以递归实现在空间效率上往往也表现糟糕。

相反，循环实现则没有上面提到的调用返回链的问题。所以在时间和空间效率上都略胜一筹。但是递归比循环适用范围广，也就是说有的算法用递归能实现，用循环却做不到（比如二叉树的遍历）。实际上，所有的循环都可以转化为一类特殊的递归，尾递归。而且，如果编译器能做尾调优化，那么用尾递归实现的算法在空间利用上则跟用循环实现持平。下面是阶乘用尾递归的实现：

unsigned long
fac2(int n, unsigned long r)
{
return (n == 0 ? r : fac2(n-1, n*r));
}

计算的时候要写fac2(3, 1);。

递归一开始是比较抽象的，要慢慢理解。如果我上面有些概念你不太明白也没太大关系，往后你会明白的。

Answer 2

//递归
int fact(int n)
{
if(n==0)return 1;
else return n*fact(n-1);
}
//递推
int fact(int n)
{
int num[100];
num[0]=1;
for(int i=1;i<=n;i++)num[i]=num[i-1]*i;
return num[n];
}

追问

谢谢

Answer 3

还有递推这种事情么，那个应该是普通的循环的别称吧。
int fact(int n)
{
int a = 1;
int i;
for(i=1;i<=n;i++)
a = a * i;
return a;
}
递归，通俗上讲就是自己调用自己
int fact (int n)
{
if(n<2) return 1;
else return n*fact(n-1);
}/*递归求N！*/

Answer 4

最基本的要知道0！和1！的值都是1，然后呢！？2！=2*1=2，3！=2！*3=2*3.。。。多想想，就会明白的！