이 재귀 함수가 반복적입니까?

Question

sicp 강연을 보았습니다. 비디오 1b에서 sussman은 algo 1을 반복적으로 호출합니다. 그는 방법 2가 반복적이라고 말한다. 내 이해에서 모두 재귀 알고리즘입니다. 방법 1을 가장 잘 생각하려면 어떻게해야합니까? 반복적 인 재귀 적 알고리즘으로서?

https://www.youtube.com/watch?v=dlbMuv-jix8

방법 1 - 시간 복잡도는 O이다 (x)는, 공간 (1)

(define (+ x y) 
     (if (= x 0) 
      y 
      (+ (-1+ x) (1+ y)))) 

방법 2 O 인 - 타임 보수는 O (x)는, 공간는 O (X)

(define (+ x y) 
    (if (= x 0) 
     y 
     (1+ (+ (-1+ x) y)))) 

Answer 1

모두 재귀하지만 계획 같은 일부 언어는 구현이 첫 번째 예제에 tail call elimination를 실시 할 것을 요구하고 있습니다. 꼬리 재귀 서브 루틴은 제어 흐름에서 마지막으로을 호출하는 서브 루틴입니다. 이러한 서브 루틴은 인터프리터/컴파일러에 의해 재구성 될 수 있으므로 스택 공간을 저장하기 위해 반복적으로 수행됩니다.

Answer 2

첫 번째 알고리즘은 표현 방법에서 재귀이지만,이 알고리즘의 마지막 — 재귀 호출 (또한 tail call라고도 함) 꼬리 재귀입니다 있습니다. 테일 재귀는 간단히 반복으로 변형됩니다. 두 번째 알고리즘에서 재귀 호출은 인수 중 하나를 평가하는 데 사용되므로 꼬리 재귀는 아닙니다.

나는 비디오를 보는데 귀찮게하지 않았지만 첫 번째 알고리즘은 반복적으로 묘사 된 것입니다.

Answer 3

첫 번째 예제는 꼬리 재귀 적이며 따라서 반복적이며 두 번째 예제는 스택을 증가시키고 그렇지 않습니다.

SICP 비디오에서 그들은 꼬리 재귀 프로 시저를 반복적으로 호출합니다. 재귀가 Scheme의 유일한 루프 메커니즘 인 경우에도 반복적이지 않은 프로 시저를 재귀 적으로 호출하는 경향이 있습니다. (do 같은 것들은 꼬리 재귀 프로 시저 호출을위한 문법적 설탕 일뿐입니다.) 꼬리 재귀 프로 시저와 반대되는 좋은 이름은 없습니다.

여전히 Sussman은 Scheme의 저자이자 SICP 서적 저자 중 한 사람이기 때문에 자신이 가장 위대한 마법사입니다. 비디오는 80 년대부터 였고 당시 보고서는 R3RS였습니다. 그들이 사용하고있는 언어가 이전 버전의 Scheme이라 할지라도 오늘날 가장 많이 사용되는 스키마 보고서 인 R5RS와 그리 멀지 않습니다.