내 기본 케이스가 잘못 되었나요? -이 알고리즘에서 수행되는 비교의 수를 캡처하는 재발 관계를 만들 필요가

Question

여러 재발와 알고리즘에 대한 재발의 관계 :

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

이 내가 생각 해낸 것입니다 -하지만 난 수없는 것 ... 내가 뭘 잘못했는지

자료 사례 파악 : M을 (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 //???????????? 

내 기본 케이스 잘못인가? 그렇다면 왜? 도와 주셔서 감사합니다. (n은 1과 같다), M은 (1) 1 (일정 시간 복잡도)로 이동해야베이스 케이스

Answer 1

,

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

Answer 2

문제는 비교의 수에 관한 것이다.

함수를 호출 할 때마다 정확하게 하나의 비교를 실행합니다.

결과가 n=1이면 완료되고 일 때 n-1으로 세 가지 순환 호출을 수행합니다. 분명히

,

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

n의 값을 증가 M를 계산함으로써, 당신은 쉽게 패턴 발견 : 생각을했다 무엇 1, 3, 9, 27, 81...