代码之家 › 专栏 › 技术社区 › Rohan Kishibe

递归调用的工作原理

recursion java

Rohan Kishibe · 技术社区 · 8 年前

我通过引用internet上的一些代码,使用递归调用编写了fizzbuzz代码。下面的代码工作正常,但我无法完全理解执行此代码时发生了什么。

更具体地说,我不明白为什么 1 首先显示。在里面 main() 方法 recurrence() 接收 100 ,所以感觉 Buzz 首先显示(结果为100)。

我在IntelliJ上调试了断点 recurrence(i - 1) ,首先调用该方法100次,然后执行其余代码。我想知道 recuurence 已存储。

public class FizzBuzz {

    public static void main(String[] args) {

        recurrence(100);
    }

    private static void recurrence(int i) {
        if (i > 1) {
            recurrence(i - 1);
        }

        if (i % 15 == 0 ) {
            System.out.println("FizzBuzz");
        } else if (i % 5 == 0) {
            System.out.println("Buzz");
        } else if (i % 3 == 0) {
            System.out.println("Fizz");
        } else
            System.out.println(String.valueOf(i));
    }
}

4 回复 | 直到 8 年前

azro 8 年前

你打电话 recurrence(100);
这需要 recurrence(99); 因为 100>1
这需要 recurrence(98); 因为 99>1
。。。
这需要 recurrence(1); 因为 2>1 -&燃气轮机;转到 else 和打印 1
然后所有其他的指纹都被打印出来了

尝试使用更简单的代码进行理解,该代码将打印出来 1 2 3 4 5 6 7 8 9 10 :

public static void main(String[] args) {
    recurrence(10);
}

private static void recurrence(int i) {
    if (i > 1) {
        recurrence(i - 1);
    }       
    System.out.println(String.valueOf(i));
}

>recurrence(10) 
  -> recurrence(9) 
    -> recurrence(8) 
      -> recurrence(7) 
        -> recurrence(6)
          -> recurrence(5)
            -> recurrence(4)
              -> recurrence(3)
                -> recurrence(2) 
                  -> recurrence(1) 
                  -> print(1)
                -> print(2)
              -> print(3)
            -> print(4)
          -> print(5) 
        -> print(6)
      -> print(7) 
    -> print(8)
  -> print(9)
-> print(10)

davidxxx 8 年前

我不明白为什么一开始显示1。在main()方法中,

因为第一次调用 100 使递归调用在此条件语句上循环 true :

if (i > 1) {
    recurrence(i - 1);
}

这是真的 recurrence(100) ,则, recurrence(99) ,则, recurrence(98) 。。。直到 recurrence(1) 。
在递归调用时( 重复(1) )在哪里 i=1 ,情况有所不同,因为单个条件语句的计算结果为 真的 是:

else
     System.out.println(String.valueOf(i));

所以 1 首先打印。

我理解为什么先打印1。1是重复(1)的结果, 但仍在努力理解其余结果的来源。我试着想想吧。

下一个输出与当前堆叠调用的“取消堆叠”相关。

调用的“unstack”按与调用相反的顺序执行。因此,您将从上次调用取消到第一次调用。

重复(100) ,则, 复发(99) ,则, 复发(98) 。。。, recurrence(2) ,则, 重复(1) 已调用并堆叠然后从 重复(1) ,则, 复发(2) 。。。, 重复(100) 。

为了简化递归调用的工作方式,请记住方法调用是堆叠的(递归或非递归),堆栈是后进先出结构。

回到解释上来 重复(1) 达成以下声明:

System.out.println(String.valueOf(i));

该方法返回,JVM继续执行上一个堆栈调用:

复发(2) 执行以下语句(前面的语句已被调用):

    if (i % 15 == 0) {
        System.out.println("FizzBuzz");
    } else if (i % 5 == 0) {
        System.out.println("Buzz");
    } else if (i % 3 == 0) {
        System.out.println("Fizz");
    } else
        System.out.println(String.valueOf(i));

喜欢 重复(1) ,计算为的单个条件语句 真的 是:

其他的
系统出来println(String.valueOf(i));

所以 2 已打印。

继续为当前堆叠的调用应用相同的逻辑 recurrence(3) ,则, recurrence(4) 直到 重复(100) 一切都应该清楚。

sander 8 年前

 if (i > 1) {
        recurrence(i - 1);
    }

此语句“重新启动”该方法,并且在i>之前不会执行下面的代码;1返回false(当i=1时第一次发生)。

至于结果存储的位置:您的方法是返回类型void,这意味着没有结果。如果您正在考虑输出,我希望您现在理解为什么它没有打印出来。

MDaniluk 8 年前

如果函数的开始

if (i > 1) {
            recurrence(i - 1);
        }

此时会调用“下一级递归”(也就是说,在每一级,您首先要做的是调用另一个递归函数),当您到达最后一级(第100级->i=1)时,您可以访问代码

if (i % 15 == 0 ) {
            System.out.println("FizzBuzz");
        } else if (i % 5 == 0) {
            System.out.println("Buzz");
        } else if (i % 3 == 0) {
            System.out.println("Fizz");
        } else
            System.out.println(String.valueOf(i));
    }

完成代码后,第100级(i=1)完成,然后是第99级、第98级,最后完成功能的是第1级(i=100)。

尝试在internet上观看一些视频(递归是如何工作的),这些视频将在演示中解释这一点,这将更容易理解。