很难理解递归

Question

  public static int fun(int n) {
    if (n<=1) return 1;
    else return (n + fun(n-1));   
  }

为什么要fun(6)回来21？

我如何可视化递归如下:

6 + 5 = 11
5 + 4 = 9
4 + 3 = 7
3 + 2 = 5
2 + 1 = 3
1       1
11 + 9 + 7 + 5 + 3 + 1 = 36

有人可以向我解释这里发生了什么吗？

- 编辑删除了System.out.println(),忘记在我发布代码时将其删除.

我自己尝试了以下方法:

public static int fun(int n) {
    if (n==1) return 2;
    else return 2 * fun(n-1);   
}

2 * fun(4)
2 * (2 * fun(3))
2 * (2 * (2 * fun(2)))
2 * (2 * (2 * (2 * fun(1))))
2 * 2 * 2 * 2 * 2 = 32

这是可视化的正确方法吗？

Answer 1

我认为将其可视化为更简单:

fun(6) =
6 + fun(5) =
6 + 5 + fun(4) =
...
6 + 5 + 4 + 3 + 2 + 1 =
21

基本上每个递归调用都会使我们更接近终止(n <= 1).只有在达到终止后才能计算最终结果

Answer 2

每次通话都会fun结束return n + fun(n-1);.让我们一步一步看看会发生什么.

你打电话给fun(6)谁......

评估6 + fun(5)哪个......

评估6 + (5 + fun(4))哪个......

评估6 + (5 + (4 + fun(3)))哪个......

评估6 + (5 + (4 + (3 + fun(2))))哪个......

计算结果6 + (5 + (4 + (3 + (2 + fun(1)))))和因为fun(1) = 1,这

评估6 + 5 + 4 + 3 + 2 + 1哪个是21.