在这个例子中无法理解递归是如何工作的

我得到了以下代码:

public int func(int n){ if(n == 1) return 2; else return 3 * func(n-1)+1; } 

我可以理解像factorial和fibonacci这样的递归,但对于这个我不能。 我试图追踪逻辑:

 if n is 3: return 3 * func(2) + 1 return 3 * func(1) + 1 return 3 * 2 + 1 return 7 

我总是以7与任何其他数字结束,我知道这是错误的,因为我在运行程序时获得了不同的值。 你能帮我理解递归是如何工作的吗?

我认为这是不言自明的,如果你需要更多的信息只是评论!

 if n is 3: return 3 * func(2) + 1 return 3 * (3 * func(1) + 1) + 1 //func(2) is equals to 3 * func(1) + 1 return 3 * (3 * 2 + 1) + 1 //func(1) is equals to 2 return 22 
  • 如果n为1则返回2 (所以func(1) = 2 )。
  • 如果n为2,则返回3 * func(1) + 1 ,即3 * 2 + 1 = 7 (因此func(2) = 7 )。
  • 如果n为3,则返回3 * func(2) + 1 ,即3 * 7 + 1 = 22 (因此func(3) = 22 )。
  • 如果n为4,则返回3 * func(3) + 1 ,即3 * 22 + 1 = 67 (因此func(4) = 67 )。

等等。 换句话说,当n = 1它只返回2,而在所有其他情况下,它返回func(n - 1)乘以3的值,并添加一个。

如果n是3

 func(3) =3*func(2)+1 =3*(3*func(1)+1)+1 =3*(3*2+1)+1 =22 

如果n是4

 func(4) =3*func(3)+1 =3*22+1 =67 

你很接近,但错过了一个关键点:

 func(3) is: 3 * func(2) + 1 func(2) is: 3 * func(1) + 1 func(1) is: 2 Therefore, func(2) is 3*2+1 = 7. And func(3) is 3*7+1 = 22 

当你得到n=3

 func(3) = > return 3 * func(2) + 1 

其中func(2)

 func(2) = > return 3 * func(1) + 1 

其中func(1)

 func(1) = > return 2 

一旦你将它们结合起来就可以了

 func(3) => return 3 * (3 * (2) + 1) + 1 func(3) => return 22 

您必须将最深层递归调用所获得的值重新输入上一级别等等。

 func(1) = 2 func(2) = 3 * func(1) + 1 = 7 func(3) = 3 * func(2) + 1 = 22 func(4) = 3 * func(3) + 1 = 67