使用Java中的递归的因子

Question

我正在使用Java:The Complete Reference这本书学习Java.目前我正在研究Recursion主题.

请注意: stackoverflow上有类似的问题.我搜索了他们,但我没有找到我的问题的解决方案.我对以下程序中的逻辑感到困惑.

如果我运行以下程序,它会产生正确的输出,但我不明白逻辑.

• 我不理解以下行中的逻辑:result = fact(n-1)*n;
• 据我所知,如果我们传递n = 4的值,如下面的程序所示,
• 然后,将3*4存储在结果中,即12.
• 再次,事实(n-1)被称为.然后n变为3.
• 然后将2*3存储在结果中,替换之前的12.

• 我想你明白我被困在哪里/困惑.

• 谢谢.

class Calculation
{
    int fact(int n)
    {
        int result;

       if(n==1)
         return 1;

       result = fact(n-1) * n;
       return result;
    }
}

public class Factorial
{
     public static void main(String args[])
     {
       Calculation obj_one = new Calculation();

       int a = obj_one.fact(4);
       System.out.println("The factorial of the number is : " + a);
     }
}

Answer 1

首先,您应该了解因子是如何工作的.

让我们4!举个例子.

4! = 4 * 3 * 2 * 1 = 24

让我们使用上面的例子模拟代码:

int fact(int n)
    {
        int result;
       if(n==0 || n==1)
         return 1;

       result = fact(n-1) * n;
       return result;
    }

在大多数编程语言中,我们都有我们所说的function stack.它就像一副牌,每张牌都放在另一张牌之上 - 每张牌都可以被认为是一种功能所以传递方法fact:

堆栈级别1: fact(4) // n = 4 and is not equal to 1. So we call fact(n-1)*n

堆栈级别2: fact(3)

堆栈级别3: fact(2)

堆栈级别4:fact(1)//现在,n = 1.所以我们从这个函数返回1.

返回值...

堆栈级别3: 2 * fact(1) = 2 * 1 = 2

堆栈级别2: 3 * fact(2) = 3 * 2 = 6

堆栈级别1: 4 * fact(3) = 4 * 6 = 24

所以我们得到24

请注意以下几点:

result = fact(n-1) * n;
           return result;

或者干脆:

return fact(n-1) * n;

这会调用函数本身.以4为例,

根据功能堆栈顺序..

return fact(3) * 4;
return fact(2) * 3 * 4
return fact(1) * 2 * 3 * 4

替换结果......

return 1 * 2 * 3 * 4 = return 24

我希望你明白这一点.

Answer 2

这是对使用递归的因子计算如何工作的另一种解释.

让我们稍微修改一下源代码:

int factorial(int n) {
      if (n <= 1)
            return 1;
      else
            return n * factorial(n - 1);
}

这是3的计算!详情:

来源:RECURSION(Java,C++)| 算法和数据结构

Answer 3

result是方法的局部变量fact.因此,每次调用事实方法时,结果都存储在与先前事实调用不同的变量中.

因此,当使用3作为参数调用fact时,您可以想象它的结果是

 result3 = fact(2) * 3
 result3 = result2 * 3
 result3 = 1 * 2 * 3

Answer 4

我相信,你的困惑来自于你认为只有一个result变量,而实际上result每个函数调用都有一个变量.因此,旧的结果不会被替换,而是返回.

详细说明:

int fact(int n)
{
    int result;

   if(n==1)
     return 1;

   result = fact(n-1) * n;
   return result;
}

假设致电fact(2):

int result;
if ( n == 1 ) // false, go to next statement
result = fact(1) * 2; // calls fact(1):
|    
|fact(1)
|    int result;  //different variable
|    if ( n == 1 )  // true
|        return 1;  // this will return 1, i.e. call to fact(1) is 1
result = 1 * 2; // because fact(1) = 1
return 2;

希望现在更清楚了.

Answer 5

public class Factorial {

    public static void main(String[] args) {
        System.out.println(factorial(4));
    }

    private static long factorial(int i) {

        if(i<0)  throw new IllegalArgumentException("x must be >= 0"); 
        return i==0||i==1? 1:i*factorial(i-1);
    }
}

Answer 6

会发生什么是递归调用本身会导致进一步的递归行为.如果你要写出来,你会得到:

 fact(4)
 fact(3) * 4;
 (fact(2) * 3) * 4;
 ((fact(1) * 2) * 3) * 4;
 ((1 * 2) * 3) * 4;