유한 연분수는 펼칠 수도 누적할 수도 있다.
같은 분자 프로시저와 분모 프로시저로 첫 항부터 펼치는 재귀적 프로세스와 마지막 항부터 쌓는 반복적 프로세스를 만들 수 있습니다.
생각해 볼 질문
평가 순서는 유한 연분수 값을 바꾸지 않으면서 프로세스의 모양을 어떻게 바꿀까요?
- 분자 프로시저와 분모 프로시저로 유한 연분수 나타내기
- 위에서 아래로 펼치는 재귀에서 미뤄지는 나눗셈 읽기
- 아래에서 위로 쌓는 반복에서 완성된 누적 결과 읽기
- 깊이와 각 항을 고정한 채 프로세스 모양 비교하기
재귀 버전은 1번 항에서 시작하지만 나머지 연분수가 돌아오기 전에는 나눗셈을 끝낼 수 없습니다. recur가 k를 향해 가는 동안 호출마다 분모 덧셈과 나눗셈 하나가 기다립니다.
반복 버전은 k번 항에서 시작하며 0.0을 이미 계산한 꼬리로 둡니다. 호출마다 result를 완성된 연분수 층 하나로 바꾸고 1번 항을 향해 갑니다. 두 예제는 분자와 분모 열 개가 모두 1.0이므로 황금비의 역수에 대한 같은 유한 근삿값을 반환합니다.
SICP 코드UTF-8 278 / 1,048,576바이트
예제
결과—
- 출력
- —
- 값
- —
- 진단
- —
실행 추적0 / 0 개 이벤트
두 프로그램은 항 열 개에서 모두 0.6179775280898876을 반환합니다.
재귀 실행에서는 나눗셈이 돌아오기 전에 recur가 k를 향해 가는 과정을 따라가세요. 반복 실행에서는 i가 줄어들 때마다 result가 완성된 꼬리 하나로 바뀌는 모습을 보세요. 고정 한도의 실행 흐름은 선택한 깊이와 항의 모든 단계를 기록합니다.
프로그램을 수정하고 결과를 비교해 보세요.
두 프로그램에서 k를 10에서 5로 바꾸세요. 두 결과가 여전히 같은지 예상하고 새로운 유한 값을 기록해 보세요.
힌트 보기
분자와 분모는 그대로 두세요. 연분수 층의 수만 줄어듭니다.