의도: 재귀 개념, 사고방식 설명.
메모:
SICP(통칭 "마법사 책") 1장과 거의 동일한 내용.
링크: https://sourceacademy.org/sicpjs/1
- 기본 표현식(primitive expressions): 언어가 다루는 가장 단순한 개체.
- 숫자(
2), 문자열("hello"), 내장 연산자(+,*) 등.
- 숫자(
- 조합 수단(means of combination): 단순한 요소들을 결합해 복합 요소를 만드는 방법.
- 예:
(+ 2 3), 함수 호출의 중첩.
- 예:
- 추상화 수단(means of abstraction): 복합 요소에 이름을 붙여 하나의 단위로 다루는 방법.
- 예:
(define (square x) (* x x))- 추상화 수준을 점진적으로 높여 나감.
- 예:
-
Applicative-order evaluation (인수 먼저 평가)
- 함수를 적용하기 전에 인수를 모두 평가함.
- Scheme, Python 등 대부분의 언어가 사용하는 방식.
- 예:
(square (+ 1 2))→(square 3)→(* 3 3)→9
-
Normal-order evaluation (필요할 때 평가)
- 인수를 평가하지 않고 표현식을 끝까지 전개한 뒤, 최종적으로 기본 연산에 도달하면 그때 평가.
- 사이드이펙트이 있으면 평가 순서·횟수가 달라져 applicative-order와 다른 결과를 낼 수 있음.
- (추가 정보) Haskell의 lazy evaluation(call-by-need)이 이 모델에 가까움.
- 단, normal-order는 같은 인수를 매번 재평가하고, lazy evaluation은 한 번 평가 후 캐싱한다는 차이가 있음.
- Haskell은 사이드 이펙트로 인한 결과 차이를 해결하기 위해 두 층으로 분리.
- 바깥층 (IO 모나드): sequencing. Applicative-order처럼 순차 실행.
- 안쪽층 (순수 계산): lazy evaluation (call-by-need). 필요할 때만 평가.
- 예:
(square (+ 1 2))→(* (+ 1 2) (+ 1 2))→(* 3 3)→9
두 방식 모두 부작용(side effect)이 없으면 동일한 결과를 산출함 (SICP §1.1.5).
sum(n) = 1 + 2 + ... + n
재귀적 프로세스 (linear recursive process):
def sum_recursive(n):
if n == 0: # base case: 재귀의 종료 조건. 없으면 무한 호출.
return 0
return n + sum_recursive(n - 1)- 호출마다
n + ...을 기억해야 하므로 콜 스택이 O(n)으로 증가. - n이 충분히 크면 stack overflow 발생.
반복적 프로세스 (linear iterative process) - 꼬리 재귀:
def sum_iter(n, acc=0):
if n == 0: # base case
return acc
return sum_iter(n - 1, acc + n) # 꼬리 위치에서 호출- 재귀 호출이 함수의 마지막 연산(꼬리 위치 = 지역 변수를 안써서 콜스택 프레임을 유지할 필요 없음)이므로, 이전 프레임을 유지할 필요가 없음.
- 단, 언어/구현체가 꼬리 호출 최적화(TCO)를 지원해야 실제로 스택이 O(1)이 됨.
SICP는 "재귀적 프로시저"와 "재귀적 프로세스"를 구분함.
문법적으로 자기 자신을 호출하는 프로시저(procedure)라도, 생성하는 프로세스(process)는 반복적일 수 있음 - 꼬리 재귀가 그 경우.
하나의 호출이 자기 자신을 두 번 이상 호출하면서 트리 형태로 전개되는 재귀.
피보나치가 대표적 예시.
- 동일한 하위 문제가 반복 계산됨. 시간 O(2^n).
- 공간은 트리 깊이만큼: O(n).
중복 계산 제거 방법: (메모는 강의에선 설명 안함.)
- 반복적 프로세스로 변환 (꼬리 재귀): 이전 결과를 accumulator로 넘기면서 밑에서 위로 계산. 트리 전개 자체가 발생하지 않음. 시간 O(n), 공간 O(1) (TCO 지원 시).
- 메모이제이션: 트리 재귀 구조를 유지하되 계산 결과를 캐싱. 시간 O(n), 공간 O(n).
재귀는 반복문과 달리 순차적으로 사고하면 안 됨. 문제를 더 작은 동일 구조의 하위 문제로 분할하는 관점이 필요함.
재귀로 풀 수 있는지 판단하는 기준:
- 문제를 더 작은 하위 문제로 쪼갤 수 있는가?
- 하위 문제들이 원래 문제와 같은 구조인가?
- 종료 조건(base case)이 존재하는가?
위 세 가지 조건을 만족하면 재귀로 풀 수 있음.
이때 재귀적 프로시저와 재귀적 프로세스의 구분을 의식할 것 - 같은 재귀 프로시저라도 꼬리 재귀로 작성하면 반복적 프로세스가 됨.
개인 메모:
재귀는 아래에서 위로(base case → 원래 문제) 올라오면서 결과를 조립함.
반복문 기반 사고를 할 때는 이 방향으로 생각하면 자연스러움.강의에서 나온 예시 모음: sum, fib, counting coin, hanoi tower
hanoi tower
- 원판 1개인 경우
- 2개 이상인 경우로 base를 구분 가능. - 위치를 하드코딩이 아니라 보조 기둥으로 생각하는 관점이 중요.
최고최고!