스키마 R5RS, 재귀 또는 반복?

Question

필자는 1에 인수를 대입하고 인수에서 1을 뺀 2 개의 함수로 구성표 코드를 프로그래밍했습니다. 이제 자동으로이를 수행하는 함수를 프로그래밍했지만 재귀 적이거나 반복적인지 여부는 알 수 없습니다. 전체 코드는 다음과 같습니다.

(define add1
  
    (lambda (x)
  
    (+ x 1))) 

(define sub1
  
    (lambda (x)
  
    (- x 1))) 

(define plus
  
    (lambda (x y)
  
    (if (zero? y)
  
     x
  
     (plus (add1 x) (sub1 y))))) 

이제 제 질문은 어떤 종류의 기능이 플러스입니까? 재귀 적 또는 반복적 인 이유와 그 이유는 무엇입니까?

Answer 1

구문 상, plus 함수는 재귀 적입니다. 분명히 자체 호출입니다. 흥미로운 질문은 어떤 종류의 프로세스을 생성합니까? tail-recursive (직관적으로 : 재귀 호출 후에 수행 할 작업이 남아 있지 않음) 형식으로 작성되었으므로 생성되는 프로세스는 반복적이라고 말할 수 있습니다. 절차 및 프로세스가 생성하는 프로세스에 대한 자세한 내용은 SICP을 참조하십시오.

Answer 2

코드가 진행되면서 재귀 적 절차가 진행됩니다. 그러나 프로세스는 꼬리 위치에서 재귀를 수행하므로 반복됩니다.

Scheme에서는 재귀 함수를 사용하여 반복적 인 프로세스와 반복적 인 프로세스를 모두 작성할 수 있습니다.

예 :

;; iterative process 
;; recursive (inner) procedure 
(define (fib n) 
    (define (fib n a b) 
    (if (zero? n) 
     a 
     (fib (- n 1) b (+ a b))) 
    (fib n 0 1)) 

;; recursive process 
;; recursive procedure 
(define (fib n) 
    (if (< n 2) 
     n 
     (+ (fib (- n 1)) 
     (fib (- n 2))))) 

계획 이러한 루프 구조가 꼬리 재귀 정말 그냥 문법 설탕은 비록 또한, 루프 구조와 재귀와 반복 두 프로세스를 작성할 수 있습니다. 더 많이 재귀 할 수 있기 위해서는 다른 언어에서도 그렇습니다.

예 :

이

;; iterative process 
;; iterative procedure (do) 
(define (fib n) 
    (do ((n n (- n 1)) 
     (a 0 b) 
     (b 1 (+ a b))) 
     ((zero? n) a))) 

;; recursive process 
;; iterative procedure (do) 
(define (fib n) 
    (let ((work (list n #f))) 
    ;; push x-1 and x-2 onto work 
    (define (push-reduce! x) 
     (set! work 
      (cons (- x 1) 
        (cons (- x 2) work)))) 
    ;; pop top of work 
    (define (pop) 
     (let ((v (car work))) 
     (set! work (cdr work)) 
     v)) 

    ;; find fibonacci with a iterative 
    ;; (and ugly) do loop 
    (do ((n 0 (if (< c 2) (+ n c) (begin (push-reduce! c) n))) 
     (c (pop) (pop))) 
     ((not c) n)))) 

마지막 하나는 피해야한다 단순히 끔찍한 계획이지만, 꽤 많은 다른 언어 스택 오버 플로우를 방지하기 위해 사용됩니다.