재귀함수

1. 개요

• 재귀함수(再歸函數, recursion)는 정의 단계에서 자신을 재참조하는 함수를 뜻한다.
• 어떤 사건이 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다. 일단 무언가를 설명할 때 자기를 포함한 것이라고 이해하면 편하다.

2. 설명

reverse [1,2,3]
= reverse [2,3] + [1]
= reverse [3] + [2,1]
= reverse [] + [3,2,1]
= [3,2,1]

reverse(s = [1,2,3])
1.  s = [1,2,3], d = [], index = 2
2.  s = [1,2,3], d = [3], index = 1
3.  s = [1,2,3], d = [3,2], index = 0
4.  s = [1,2,3], d = [3,2,1], index = -1
5. return d

qsort [] = []
qsort (p:xs) = qsort [x | x<-xs, x<p] ++ [p] ++ qsort [x | x<-xs, x>=p]

• qsort에 빈 리스트를 대입한 결과는 빈 리스트이다.(종료조건)
• qsort에 임의의 리스트를 집어넣을 경우, 리스트 맨 앞의 값을 기준으로 그보다 작은 것, 그리고 뽑은 값, 그리고 뽑은 값보다 크거나 같은 값으로 이루어진 세 개의 리스트를 만들고 그 셋을 붙이는데 첫 번째 리스트와 세 번째 리스트는 qsort 자기 자신으로 다시 처리한다.

3. 예시

3.1. LISP

#!syntax lisp
(defun fibonacci-recursive (n)
  (if (< n 2)
      n
     (+ (fibonacci-recursive (- n 2)) (fibonacci-recursive (- n 1)))))

3.2. Prolog

fib(0, R0, _, R0).
fib(N, R2, R1, RF) :-
        N1 is N - 1,
        R is R2 + R1,
        fib(N1, R1, R, RF).
fib(N, RF) :- fib(N, 0, 1, RF).

3.3. 자바스크립트

#!syntax javascript
function factorial(n) {
  if (n > 1) {
    return n * factorial(n-1);
  }  
  return 1;
}

window.onload = function () {
  document.write(factorial(5));
}

3.4. C++

#!syntax cpp

#include <iostream>

using namespace std;

int factorial(int n);
int main() {
	int n, res;
	cin >> n;
	res = factorial(n);
	cout << res;
}

int factorial(int n) {
	if (n == 1) {
		return n;
	}
	return n * factorial(n - 1);
}

3.5. 하스켈

fac 0 = 1
fac n = n * fac (n-1)

3.6. OCaml

let rec factorial n =
  if n = 1 then 1 else n * factorial (n - 1)

4. 기타

5. 비유

6. 재귀적 정의

7. 꼬리 재귀 함수

let rec last l =
  match l with
  | [a]   -> a
  | _::tl -> last tl (* tail-recursive call *)

last [x]    = x
last (_:xs) = last xs

8. 여담

• 세상에서 제일 위험한 꿈은 꿈을 꾸는 꿈이라 하였다. 영화 인셉션에서 이 소재를 다루고 있다.(오죽했으면 재귀적 구조가 나오면 -셉션이라는 접미사를 붙이는 드립이 성행했을 정도. 이런 재귀적 구조는 크리스토퍼 놀란이 즐겨 쓰는 소재이다.)
• 프랙탈이라는 특수한 도형은 패턴이 재귀적으로 반복되기 때문에, 넓이(또는 부피)는 유한하지만 길이(또는 겉넓이)는 무한하다는 괴상한 성질을 갖고 있다. 프랙털 도형은 1차원, 2차원 같은 정수 차원이 아니라 1.5차원 같은 실수 차원에 존재한다.
• 0으로 나누기 역시나 구형 계산기에서는 이 일이 일어난다.
• 재귀 함수는 치환이 무한히 이루어지기 때문에 인라인 함수로 사용할 수 없다.

9. 관련 문서

• 재귀함수

10. 외부 링크

• https://prl.korea.ac.kr/courses/cose212/2023/pl-book.pdf