理解基本递归

Question

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

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

我直接在这里写了上面的内容,所以可能无法编译,但认为它确实如此.

任何人都可以简单地解释它是如何工作的,它是如何存储的？它首先计算5*(5-1),然后下降到4*(4-1)然后3*(3-1).....直到它变为1,它将刚刚返回1？抱歉这么粗略我只想知道这是如何工作的

谢谢

但随着它的运作 - 它获得了各个阶段的价值

5*(5-1)4*(4-1)...... ......

这些如何存储然后检索回来或者我错过了什么？

Answer 1

想象一下,你就是电脑,有人会给你一张纸

factorial(3)

写在上面.然后执行该过程,查看参数.因为它是> 1,你写

factorial(2) 

在另一张纸上,"把它交给你自己",等到你得到答案之前再继续.

再次执行该过程.由于2仍然> 1你写

factorial(1)

在另一张纸上把它递给自己,等到你得到这个答案后再继续.

再次,您执行该过程.这次输入是1,所以你取第一个分支并返回1.处理factorial(2)的调用现在有一个答案,所以它将2乘以该答案(1)并返回.现在,处理factorial(3)的调用得到它的答案(2)并将它乘以3,得到6.然后它将该答案返回给开始整个操作的人.

如果你想象你在工作时把纸片放在你面前的堆栈中,那就是计算机内存中"堆栈"的可视化.每个递归调用将参数(和任何临时变量)存储在它自己的纸张(堆栈框架)上,就像纸张一样排列为下推堆栈,一个在另一个上面.

Answer 2

是的,你在代码中拥有它,它首先检查n它是否小于或等于1的值,这就是所谓的基本情况.它们很重要,它们会告诉您的递归函数何时停止.

如果值n不小于或等于,则返回的值n乘的递归调用factorial,但与价值 n-1,直到它达到它的基本情况:if (n <= 1)它返回1

您的基本案例是由因子定义设置的,0!并且1!均等于1.

也许这个图可能有助于理解调用的工作原理.

5 * fact(5-1) ->
          4 * fact(4-1) ->
                    3 * fact(3-1) ->
                              2 * fact(1) 
                                       1

哪个与5!或相同5 x 4 x 3 x 2 x 1

希望这可以帮助.

Answer 3

你在问内部的递归是如何工作的吗？一句话的答案是每个线程都有一个"调用堆栈",每次调用一个方法时,一个新的条目被推送到这个堆栈,它有关于调用哪个方法的信息,以及参数是什么.方法完成后,它将返回值放回同一堆栈,调用方法将其拉出.所以在它的高度你的堆栈看起来像

阶乘(1)称为阶乘(2)称为阶乘(3)称为阶乘(4)称为阶乘(5)

关于调用堆栈的维基百科文章乍一看似乎非常彻底.

Answer 4

1. 在对factorial的初始调用中,n = 5,并被推入堆栈.
2. 然后触发else以使4传递给阶乘,并且也被推入堆栈.
3. 然后触发else以使3传递给阶乘,并且也被推入堆栈.
4. 然后触发else以使2传递给阶乘,并且也被推入堆栈.
5. 然后触发else,因此1传递给阶乘,并且也被推入堆栈.
6. 然后触发else,因此0传递给阶乘,并且也被推入堆栈.
7. if被触发,1返回到调用阶乘.
8. if被触发并且2*1被返回到调用阶乘.
9. if被触发并且3*2被返回到调用阶乘.
10. if被触发并且4*3被返回到调用阶乘.
11. if被触发并且5*4被返回到调用阶乘.

堆栈也会被清理干净,但是输入过于繁琐.基本上,方法调用中的所有值都被压入堆栈,并在方法返回时弹出堆栈.这使它们在递归调用之间分开.