자바스크립트로 배우는 SICP - 4. 함수와 과정, 그리고 복잡도
함수와 과정의 차이점, 재귀적 vs 반복적 vs 트리 과정의 차이점 및 자원 활용도를 알아보자!
2023-10-26 | 독서 | 10min
키워드
오늘의 키워드는 다음과 같다.
- 함수 vs 과정
- 재귀적 과정 vs 반복적 과정
- 재귀 함수 vs 재귀적 과정
- 트리 재귀 vs 반복적 과정
- 증가 차수
그럼 하나씩 키워드 중심으로 살펴보자
함수와 과정
1장의 가장 처음에 등장한 계산적 과정 이라는 단어를 다시 돌아보자.
계산적 과정은 어떤 구체적인 산술 계산을 수행하는 과정보다는 좀 넓은 개념으로, “그 과정의 세부절차 단계들을 명확히 규정할 수 있으며 형식화할 수 있”는 과정을 말한다.
즉, 계산적 과정에는 세부절차 단계들이 정해져야 한다. 함수는 이러한 계산적 과정의 전개에 대한 패턴에 해당한다. 그 중 지역적 전개 패턴의 경우, 이전 단계를 기반으로 다음 단계가 어떻게 구축되는지를 명시한다. 만약 과정의 전반적인 과정을 모두 서술한다면 이는 전역 행동 방식 에 관한 패턴이라고 할 수 있다.
재귀적 과정과 반복적 과정
이 두 개념의 비교에서 집중해야 하는 것은 바로 “과정”이다. 이를 재밌게 다룰 예시로 factorial 을 들어보자!
factorial 를 구현하는 코드는 아래와 같다
function factorial(n) {
return n === 1
? 1
: n * factorial(n - 1);
}
factorial(5); // 120위의 코드가 동작하는 방식을 나열하면 다음 그림과 같을 것이다.
위와 같은 방식을 재귀적 과정 이라고 부른다. 또한, 해석기는 입력값에 비례하는 이전의 단계를 기억해야 하기에 이를 선형 재귀적 과정 이라고 부른다.
여기서 조금 다른 접근을 해보자. 위의 접근은 자바스크립트 해석기로 하여금 이전의 인수 평가 결과를 기억하고 있어야 한다. 이를 명시적으로 전달할 수는 없을까? 즉, 매 단계의 상태를 기록하는 방식으로 함수를 작성하면 다음과 같을 것이다.
function factorial(n) {
return fact_iter(1, 1, n);
}
function fact_iter(product, counter, max_count) {
return counter > max_count
? product
: fact_iter(counter * product,
counter + 1,
max_count);
}
factorial(5); // 120같은 결과를 반환하지만, 그 과정에서는 매우 큰 차이가 있다. 과정의 그림은 아래와 같다.
이 과정의 경우는 전개되거나 축약되는 과정이 존재하지 않는다. 이러한 과정을 반복적 과정 이라고 부른다.
재귀적 과정 vs 재귀 함수
재귀 함수와 재귀적 과정을 혼동하지 말아야 한다.
재귀 함수는 함수 선언에서 함수가 함수 자신을 참조한다는 구문 상의 사실을 말하는 것이다.재귀적 과정은 함수의 작성 형태와는 무관하다. 함수의 평가가 이루어지는 방식을 보고 판단하는 것이다.
이해하기 쉽게 말하자면, 재귀 함수로 작성해도 재귀적 과정이 아닐 수 있다는 것이다. 재귀 함수가 재귀적 과정이 아닌 반복적 과정을 보여줄 수 있다. 대표적인 예시는 위에서 본 fact_iter 함수이다!
트리 재귀 vs 반복적 과정
트리 재귀와 반복적 과정을 비교하는 재밌는 예시로는 피보나치를 들 수 있다! 그 유명한 피보나치의 점화식은 다음과 같다.
이를 코드로 표현하면 아래와 같다.
function fib(n) {
return n === 0
? 0
: n === 1
? 1
: fib(n - 1) + fib(n - 2);
}
fib(6); // 8위 처럼 구현된 함수는 아래와 같은 트리 재귀 과정을 거쳐 평가 및 연산이 이루어질 것이다.
유감스럽게도 이 구현이 효과적(effective으로 제대로 된 결과를 도출한다는 의미이다)이지만 효율적인 구현은 아니다. 위 그림에서 볼 수 있듯 fib(3) 을 연산하는 과정이 두 번이나 반복되는 것이다. 이는 비효율적인 자원 활용에 해당한다.
그러면 개선할 수 있는 방안은 없을까? 바로 앞서 소개한 반복적 과정 을 이용하는 것이다.
이를 구현하기 위해 기억을 다시 꺼내보자. 상태를 기록하며, 상태 갱신 규칙이 필요하고, 종료 판정 규칙이 필요하다.. 우선 상태를 두 개 마련한다. a 와 b 라고 하자. 각 상태들은 연속된 두 피보나치 수의 상태를 기록한다. (1번!)
다음으로 상태 갱신 규칙이 필요하다. 이는 a + b 연산의 결과를 a에 기록하고, a를 b에 기록한다. 여기서 a + b는 두 상태 직후의 상태를 기록하는 과정이며, 두 고정 상태를 설정했으므로 이전의 과정을 기록하기 위해 b에 a를 넣는 것이다. b → a → a + b 순서라고 보면 된다!
이를 구현한 코드는 다음과 같다.
function fib(n) {
return fib_iter(1, 0, n);
}
function fib_iter(a, b, count) {
return count === 0
? b
: fib_iter(a + b, a, count - 1);
}
fib(6); // 8역시 같은 결과가 나온다!
그런데 조심할 점은, 언제나 반복적 재귀가 맞다는 것이 아니라는 점이다. 물론 피보나치의 경우 반복적 과정이 더욱 효율적이지만, 사실 점화식을 그대로 옮겨놓은 트리 재귀적 과정이 이해하기 훨씬 편했을 것이다.
그렇지만, 위와 같은 수치 문제가 아닌 위계적 구조의 데이터를 다루는 경우, 트리 재귀가 강력하고 자연스럽다. 애초에 자바스크립트 해석기가 (2+46)(3+12) 라는 복합 연산 표현식을 평가하는 과정에서 트리 재귀를 이용한다.
증가차수
증가 차수는 입력이 커짐에 따라 과정이 요구하는 자원의 양을 대략 측정한 것이다.
증가 차수는 문제의 크기가 변함에 따라 과정의 행동이 어떻게 변할 것인지 예측하는 데 유용한 정보를 제공한다.
앞서 재귀적 과정에서 자원의 활용에 관련한 이야기를 언급했을 것이다. 계산적 과정의 종류나 성격에 따라 계산 자원을 소비하는 속도가 다를 경우 증가 차수는 이를 서술할 때 편리함을 제공해준다. 흔히 논하는 복잡도가 자원에 관련되었다고 보면 된다.(공간 복잡도이다.) (세타(n)으로 작성하지만 자세한 내용은 생략하겠다. 이와 관련해서는 아래의 링크를 참고 바란다.)
[알고리즘] 알고리즘의 이해 - 시간 복잡도 함수의 차수, 점근적 표기법, 알고리즘 최종 요약(Algorithm Understanding - D
앞서 언급했던 팩토리얼을 재귀적 과정으로 해결하는 경우, 단계의 수는 n에 비례하며(세타 n), 자원 또한 이전의 단계를 기억해두어야 하니 n에 비례할 것이다(세타 n). 반면, 반복적 과정으로 해결하는 경우, 단계의 수는 세타 n이지만, 이전의 과정들을 기억해둘 필요가 사라지므로 세타 1(상수) 에 해당한다.
트리 재귀로 보았던 피보나치의 경우, 단계의 수는 지수에 n이 있을 것이다. 즉, 세타 의 형태일 것이다. (a는 황금비 이지만 이 내용은 책 연습문제를 모아놓는 글에서 다뤄볼 예정이다.) 이는 점화식을 통해 매 상태마다 두 개씩 상태를 만들어 내는 것에서 유추할 수 있다. 자원의 경우 세타 n일 것이다. 왜냐하면, 계산의 임의의 지점에서 트리의 현재 수준보다 위에 있는 노드들만 기억하면 되기에 트리의 최대 깊이가 필요한 공간이 될 것이다.
마무리
이렇게 책너두 챌린지 범위의 키워드 중심으로 내용을 정리해보았다. 앞으로 이렇게 읽은 범위를 되돌아보는 방식으로 글을 써볼까 한다. 물론 위 내용과 더불어 좋은 연습문제들이나, 수학 공식들, 알고리즘 문제들이 여럿 등장한다. 이에 관련해서 연습 문제 만을 정리해놓은 섹션을 하나 추가로 만들까 싶다. 쨋든 오늘도 수고했다!