JS로 배우는 SICP(3) - 재귀함수 시간복잡도 줄이기

function times(a,b){
return b === 0
? 0
: a + times(a, b -1 )
}

times(10,10);

function times2(a,b){
return b === 0
? 0 :
isEven(b)
? a + times2(a,b/2) + times2(a,b /2 )
:a + times2(a, b -1 )
}

위 함수의 시간 복잡도는 b를 가진다.
아래의 함수는 logb

조건문을 추가함으로서 훨씬더 효율적인 함수가 된다.

거듭 제곱에 대한것도 추가하면

function fast_expt(b,n){
return n === 0
?1
:isEven(n)
?square(fast_expt(b,n/2)
:b * fast_expt(b, n -1 );
}