Не могу понять, как работает рекурсия в этом примере

Question

я получил следующий код:

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

Я могу понять рекурсию в таких вещах, как факторный и Фибоначчи, но для этого я не могу. Я попытался проследить логику:

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

Я всегда в конечном итоге с 7 с любым другим числом, и я знаю, что это неправильно, потому что я получаю различные значения при запуске программы. Можете ли вы помочь мне понять, как здесь работает рекурсия?

Answer 1

Я думаю, что это само собой разумеющееся, если вам нужна дополнительная информация, просто комментарий!

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 

Answer 2

если п 3

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

если п 4

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

Answer 3

Вы близки, но отсутствует ключевой момент:

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 

Answer 4

Вы должны повторно запустите то значение, которое вы получите для самого глубокого вызова рекурсии на предыдущий уровень и так далее.

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

Answer 5

• Если 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) раз три и с одним добавленным.

Answer 6

когда 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