2.2.2 · 계층적 데이터

재귀는 데이터의 모양을 따라간다.

트리에서는 모든 노드에서 같은 질문을 합니다. 비어 있는지, 더 탐색할 순서쌍인지, 아니면 바꿀 잎인지 확인합니다.

생각해 볼 질문

하나의 프로시저가 트리의 모든 깊이에서 어떻게 동작할까요?

잎과 가지 사례 구분하기
트리의 모양을 유지하며 새 트리 만들기
고정된 깊이 대신 구조적 재귀 사용하기

scale-tree는 층 수를 세지 않습니다. 순서쌍을 만나면 두 부분에 같은 프로시저를 적용하고 잎을 만나면 숫자 연산을 수행합니다.

제어 구조가 데이터 정의와 같은 모양을 가집니다. 그래서 얕은 리스트와 깊게 중첩된 트리를 깊이마다 따로 처리하지 않고 같은 프로시저로 다룰 수 있습니다.

SICP 코드UTF-8 269 / 1,048,576바이트

(begin
  (define (scale-tree tree factor)
    (cond ((null? tree) '())
          ((pair? tree)
           (cons (scale-tree (car tree) factor)
                 (scale-tree (cdr tree) factor)))
          (else (* tree factor))))
  (scale-tree '(1 (2 (3 4) 5) (6 7)) 10))

예제

결과—

출력: —
값: —
진단: —

실행 추적0 / 0 개 이벤트

예상 결과

첫 프로그램은 (10 (20 (30 40) 50) (60 70))을 반환합니다.

실행 추적에서 볼 점

프로세스가 car와 cdr 두 갈래의 일로 나뉘는 지점을 찾아보세요. 마지막 중첩 구조는 이런 구조적 결정을 되풀이한 기록입니다. 실행 흐름은 선택한 한 실행의 모든 구조적 분기를 기록합니다.

직접 해보기

프로그램을 수정하고 결과를 비교해 보세요.

count-leaves를 정의하세요. 빈 리스트에서는 0, 순서쌍에서는 두 가지 결과의 합, 나머지 잎에서는 1을 반환하게 하세요.

힌트 보기

scale-tree와 같은 세 가지 분류를 쓰되 잎에서 하는 연산만 바꾸세요.

이 수업 완료하기

이 장의 총 20개 수업 중 0개 완료0%