这个递归函数老是出错，求帮助。另外不懂递归的机制，明明没有循环，为何能多次运算

fengzhenging

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
    int fac(int n)
    int n;
    int y;
    printf("input an integer number:");
    scanf("%d",&n);
    y=fac(n);
    printf("%d!=%d\n",n,y);
    system("pause");
    return 0;
}
int fac(int n)
{
  int f;
  if(n<0)
     printf("n<0,data error")
  else if(n==0||n==1)
     f=1;
  else f=fac(n-1)*n
  return(f);
}

rosynirvana

错在你漏了3个分号，第6,20,23行
比如你要计算fac(3)
首先 f=3 > 1
所以fac(3) = fac(2) * 3
f = 2 > 1
fac(2) = fac(1) * 2
f = 1 == 1
fac(1) = 1
把上面的式子合并，有 fac(3) = 1*2*3
就是这样子实现的

从计算理论的角度来说，递归才是更本质的，循环只是递归的一种特例（尾递归）。一种计算机语言可以没有循环的语法特性，也能完成所有计算。

最后这个fac函数的实现不好，每次都要判断n是不是小于0，如果把这件事情交给调用函数来做，效率能提高不少

fengzhenging

rosynirvana 发表于 2013-6-3 11:19
错在你漏了3个分号，第6,20,23行
比如你要计算fac(3)
首先 f=3 > 1

不太理解递归才是更本质的，感觉递归一般都可以用循环来做

rosynirvana

fengzhenging 发表于 2013-6-3 13:20
不太理解递归才是更本质的，感觉递归一般都可以用循环来做

所有递归都可以有非递归的实现，但是一般来说递归的形式会简单很多。
或许说递归更本质不大确切，但是如果是教科书的叙述顺序，递归的形式更简单，形式更统一，一般是放在前面叙述的。

你说的能互相转化的，一般是这种尾递归的形式，例如(如果不理解就像上面的例子一样手动trace一下)

1. int sum(int lower, int upper, int step)
   
2. {
   
3.   if(lower >= upper) return lower;
   
4.   else return sum(lower+step, upper, stap);
   
5. }

复制代码

它等价于一个非递归的形式

1. int sum=0 , i;
   
2. for(i = lower; i < upper; i+=step)
   
3.   sum += lower;

复制代码

如果是处理一个树，想写出非递归形式就非常复杂了（可能的，但是几乎没人那么做）