프로그래밍 언어론 6-6강. 재귀(Recursion)

 

[재귀(Recursion)]

: 스스로의 subroutine을 호출함으로써 수행하는 방식의 알고리즘

: 특별한 문맥이 필요하지 않다.

: 재귀를 사용하려는 언어들은 자기들의 subroutine(함수등)을 스스로 call 가능하거나, 다시 스스로를 call 할수있는 다른 함수를 호출할 수 있어야 한다.

: 앞서 알아본 반복 알고리즘과 반대되는 개념

 

 

 

[여러언어에서의 반복과 재귀]

# Fortran 77 등 : 재귀 허용 X

# 몇몇 함수형 언어 : 반복 허용 X

# 대부분의 현대 언어들 : 두 매커니즘 둘다 지원

 

 

 

[반복과 재귀(Iteration and Recursion)]

- 반복(Iteration) : 명령형 언어에서 반복적인 변수들의 수정을 기반으로 두고있기에 보다 자연스러운 방식이다.  (반복이 자연스러운 경우 예시 : 1~10까지의 합 계산) 

- 재귀(Recursion) : 함수형 언어에서 변수들의 값을 수정하지 않기때문에 보다 자연스러운 형태이다.  (재귀가 자연스러운 경우 예시 : 최소공배수 계산 (gcd(a,b)))

: 물론 서로의 방법으로도 문제를 해결 할 수 있다.

 

 

 

[꼬리 재귀(Tail Recursion)]

: 일반적인 재귀의 방식은 실행되며 함수가 호출된 위치를 기억하고 이를 스택에 저장해둬야 한다. (재귀가 반복보다 비효율적인 주요 원인)

: 꼬리 재귀는 추가 연산이 재귀적 호출을 따라가지 않는 재귀방식을 의미한다.

: 코드상에선 해결되어보이진 않지만, 컴파일러가 이러한 꼬리 재귀로 작성된 코드를 반복문으로 바꿔준다.

# 기존 재귀 함수와 꼬리 재귀 함수 예시 - GCD문제

int gcd(int a, int b) {   if (a == b) return a;   else if (a > b) return gcd(a-b, b);   else return gcd(a, b-a); }

int gcd(int a, int b) { start:   if (a == b) return a;   else if (a > b) { a = a - b; goto start; }   else { b = b - a; goto start; } }

: 이 방식을 사용하면 실행시점에 동적 할당될 스택 공간이 필요없이, 사용중인 공간을 재사용하면 된다.

: 종종 특정 함수가 꼬리 재귀방식의 코드가 아니더라도 꼬리 재귀방식으로 변환시켜주기도 한다.

 

# 스키마에서 재귀 코드를 꼬리 재귀 방식으로 변환 예시 (프로그래머나 컴파일러가 변환해줌)

(define summation   (lambda (f low high)     if (= low high)        (f low)        ; then part        (+ (f low) (summation f (+ low 1) high ))))) ; else part

(define summation   (lambda (f low high subtotal)     if (= low high)        (+ subtotal (f low))        (summation f (+ low 1) high                        (+ subtotal (f low))))))

: 재귀를 위한 스택 할당 X

+) 위 코드에서 subtotal 이라는 파라미터를 초기 호출에 명시하고 싶지 않으면 "helper" 함수를 이용해 숨길수 있다.(생략)

 

 

 

[Applicative-Order Evaluation and Normal-Order Evaluation]

1) Applicative-Order Evaluation

  : 인자들이 subroutine에 전달되기전에 평가되는 방식 (지금까지 본 방식들)

2) Normal-Order Evaluation

  : subroutine에 평가되지 않은 인자들(unevaluated arguments)들이 전달되어, 값이 필요할때만 평가되는 방식

  : 매크로에서 일반적으로 발생 / 부울 단락 평가에서 call-by-name 파리미터와 특정 함수형 언어가 이에 해당

  : Algol 60이 사용자 정의 함수에 대해 디폴트로 이 방식 사용

 

 

 

[Lazy Evaluation]

: 표현식의 값이 필요할때까지 표현식의 평가를 지연시키는 방법.

: 일반적으로 명확성과 효율성의 측면에서 applicative 방식이 normal 방식보다 더 좋다.

: 하지만 normal-order evaluation(Lazy Evaluation)은 빠른 코드를 유도할수 있거나 applicative-order evaluation이 실행시점 오류를 발생시킬 코드에 대해서 유도할 수 있다.

: 또한, 필요하지 않는한, 전체 인자들을 한번에 계산하지 않는다.