Является ли мой базовый случай неправильным? - рекуррентное соотношение для алгоритма с множественными рецидивами

Question

мне нужно создать рекуррентное соотношение, чтобы захватить количество сравнений, выполняемых в этом алгоритме:

Func(n) 
    if n = 1 
     print "!" 
     return 1 
    else 
     return Func(n-1) * Func(n-1) * Func(n-1) 

Это то, что я придумал, - но я не могу показаться, выяснить, что я сделал неправильно ...

базовый случай: М (1) = 0

M(n) = 3[M(n-1)] 
= 3[3[M(n-2)]] 
= 3[3[3[M(n-3)]]] 
= 3^i[M(n-i)] 

i = n-1 //to get base case 

M(n) = 3^(n-1)[M(n-(n-1))] 
= 3^(n-1)[M(1)] 
= 3^(n-1)[0] 
= 0 //???????????? 

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

Answer 1

В случае базы (п равно 1), М (1) следует рассматривать как 1 (временную сложность постоянной),

M(n) = 3^(n-1) then 

Answer 2

Речь идет о количестве сравнений.

Каждый раз, когда вы вызываете функцию, вы выполняете ровно одно сравнение.

Когда результат n=1, все готово, и когда результат n>1, вы выполняете три рекурсивных звонка с n-1.

Очевидно,

M(1) = 1 
M(n) = 3 M(n-1) 

Вычисляя M для увеличения значения n, легко заметить закономерность: 1, 3, 9, 27, 81...