在这个例子中无法理解递归是如何工作的
我得到了以下代码:
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