有关于递归的问题.

xiaofanac66

long fun(int n);
void main()
{
int n = 5;
int sum = fun(n);
printf("%lld",sum);
}
long fun(int n)
{
if(n==1) return 1;
return fun(n-1)*n;
}
这例题我考虑了一个多小时真的是一点思路都没有，请问这个该怎么理解。
谢谢！

hxs554f

#include <stdio.h>
long fun(int n);
void main()
{
        int n = 5;
        int sum = fun(n);
        printf("%lld",sum);
}
long fun(int n)
{
        if(n==1)
        return 1;           //1
        return fun(n-1)*n;  //2
}
/*
第一次调用fun时n=5,根据if判断执行第2条语句(也就是sum=fun(4)*5)。
计算fun(4)时第二次调用fun，此时n=4,根据判断还是执行第2条(也就是fun(4)=fun(3)*4)。
依此类推,fun(3)=fun(2)*3,fun(2)=fun(1)*2。最后计算fun(1)时执行第1条得fun(1)=1;
*/

莫名其妙

long fun(int n)
{
if(n==1) return 1;
return fun(n-1)*n; 关键就在这里  这里返回值里还在调用函数 fun(int n )   
  我在在去研究下反汇编代码  看看当n=1 以后为什么在下面return fun()*n 会继续加回去 !~像是返回了5次!~

明白了
         当n=5    调用函数 fun(5) 然后执行 if(n==1) return 1; return fun(n-1)*n这里又调用了一次函数 这里调用的是fun(5-1)
相当于 n=4     调用函数 fun(4) 然后执行 if(n==1) return 1; return fun(n-1)*n这里又调用了一次函数 这里调用的是fun(4-1)
相当于 n=3     调用函数 fun(3) 然后执行 if(n==1) return 1; return fun(n-1)*n这里又调用了一次函数 这里调用的是fun(3-1)
相当于 n=2     调用函数 fun(2) 然后执行 if(n==1) return 1; return fun(n-1)*n这里又调用了一次函数 这里调用的是fun(2-1)
相当于 n=1     调用函数 fun(1) 然后执行 if(n==1) return 1; 这里 条件符合返回 1  然后逐层返回     这里返回 值为1
现在是跳回到 n=2   那一行   return fun(n-1)*n   这个fun(n-1)现在是刚才返回的值1 然后相当于 return  1*n     然后这里return的值为1*2=2
现在跳回到    n=3 那一行     return fun(n-1)*n   这个fun(n-1)现在是刚才返回的值2  然后相当于 return  2*n     然后这里return的值为2*3=6
现在跳回到    n=4 那一行     return fun(n-1)*n   这个fun(n-1)现在是刚才返回的值6  然后相当于 return  6*n     然后这里return的值为6*4=24
现在跳回到    n=5 那一行     return fun(n-1)*n   这个fun(n-1)现在是刚才返回的值24 然后相当于 return  24*n     然后这里return的值为24*5=120   然后到这里才是真正返回到主函数中的sum

xiaofanac66

莫名其妙 发表于 2012-4-1 17:53

                               
登录/注册后可看大图

long fun(int n)
{
if(n==1) return 1;

首先谢谢您认真的回答！{:1_1:}，但是我还有些地方不明白，我只知道，如果N不等于1的话N本身就自减一直到等于1为止，然后后面的就很模糊了，真的不理解N又是怎么从1自加回去的！还请您慢慢道来！谢谢！

bananazzl

很复杂，思路还没能理解

莫名其妙

xiaofanac66 发表于 2012-4-1 18:38

                               
登录/注册后可看大图

首先谢谢您认真的回答！，但是我还有些地方不明白，我只知道，如果N不等于1的话N本身就自减一直到 ...

我用我的思路感觉上面的回答应该很清楚了
你已经明白他会一直 -1 减到为1的时候就停止
我感觉可以这么写代码 假设现在n已经减到1了 开始执行return 1
    return    fun( ( fun(( fun(( fun((fun(n-1)*n)-1)*n)-1)*n)-1)*n)-1)*n   
每种颜色就是一个返回值     将结果返回到调用他的相关函数中去
借用3楼的说法吧
sum 调用了fun(5),
fun(5)=fun(4)*5).而fun(4)=fun(3)*4 .   fun(3)=fun(2)*3 . fun(2)=fun(1)*2 .  而fun(1) 这里执行if 语句 return 1
然后成就就吧  fun(1)=1 返回到  fun(2)=fun(1)*2 → fun(2)=1*2 结果fun(2)=2
然后在吧fun(2)=2       返回到fun(3)=fun(2)*3)→fun(3)=2*3 结果 fun(3)=6
然后在吧 fun(3)=6   返回到 fun(4)=fun(3)*4→ fun(4)=6*4  结果 fun(4)=24
然后在吧 fun(4)=24 返回到  fun(5)=fun(4)*5→ fun(5)=24*5 结果 fun(5)=120
fun(5)呢正好是 sum 的值

仰望天上的光

用不完全归纳法来想：
(1)假设f(n)表示n的阶乘
(2)当n==1的时候f(1)==1,(1)成立
(3)假设f(k)为k的阶乘k>=1
(4)则f(k+1) = (k+1)*f(k)所以f(k+1)为k+1的阶乘
(5)所以f(n)表示n的阶乘

湮汐

做递归的时候，尽量先把递归的功能搞懂，就像楼上所说的。一般都有一个规律，或者是数学公式。如果是简单的，递归深度不深的还好，但是如果深度比较大的，就不方便一个个的列出来的。

bisoo

感谢几位大侠的讲解，受教了！{:1_1:}

wangying1357

我觉得递归就是给几个关系式，让程序自己去得结果。就像数列一样。如a0=a1=1,an=a(n-1)*n;求n=某值时an的值，计算机可以由关系式求出结果（由某值至1一次次的展开关系式计算），ok

刺客信条

感谢几位大侠的讲解，受教了