재귀함수

리듬게임 수록곡에 대한 내용은 リカーシブ・ファンクション 문서 참고하십시오.

수학기초론 Foundations of Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px"	다루는 대상과 주요 토픽
수리논리학	논리 · 논증{ 귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{ 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문( 조각적 정의) · 명제 논리( 명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리( 존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론
집합론	집합( 원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계( 동치관계 · 순서 관계) · 순서쌍( 튜플) · 서수( 하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC( 선택공리) · 기수( 초한기수) · 절대적 무한 · 모임
범주론	범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성
계산가능성 이론	계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수
정리
드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리( 괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리
기타
예비사항( 약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학
틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보		}}}}}}}}}

''' 이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"'''
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px"	<colbgcolor=#aa3366> 이론
기본 대상	수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론	재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버
	오토마타 이론	FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임
계산 복잡도 이론	점근 표기법 · 튜링 기계^^{고전, 양자, 비결정론적, 병렬 임의접근 기계}^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법)
정보이론	데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
프로그래밍 언어이론	프로그래밍 언어( 함수형 언어 · 객체 지향 프로그래밍) · 메타 프로그래밍 · 형식언어 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론
주요 알고리즘 및 자료구조
기초	정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현	배열^^벡터^ · 리스트^^{연결 리스트}^ · 셋(set)^^{레드-블랙 트리, B-트리}^ · 우선순위 큐^^{힙, 피보나치 힙}^
수학적 최적화	조합 최적화	외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
	볼록 최적화	내부점 방법 · 경사하강법
	선형계획법	심플렉스법
계산 수론 및 암호학	밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시( MD5 · 암호화폐 · 사전 공격( 레인보우 테이블) · SHA) · 양자 암호
	대칭키 암호화 방식	블록 암호 알고리즘( AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
	공개키 암호화 방식	공개키 암호 알고리즘( 타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
계산기하학	볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^^{Fortune의 line-sweeping 알고리즘}^ · 범위 탐색^^{vp-tree, R-tree}^ · k-NN
그래프 이론	탐색^^{BFS, DFS, 다익스트라 알고리즘, A* 알고리즘}^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제^{대각선 논법} · 암달의 법칙 · P-NP 문제^미해결 · 콜라츠 추측^미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학			}}}}}}}}}

1. 개요2. 설명3. 예시

3.1. 자바스크립트3.2. C++

4. 기타5. 재귀적 정의6. 관련 문서

1. 개요

재귀함수( 再歸函數, recursion)는 정의 단계에서 자신을 재참조하는 함수를 뜻한다.

어떤 사건이 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다. 일단 무언가를 설명할 때 자기를 포함한 것이라고 이해하면 편하다.

2. 설명

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다. 재귀 호출이나 되부름이라고도 한다.

이 문단의 제목에 걸려 있는 링크를 클릭하는 것은 재귀함수의 동작과 동일하다.[1] 물론 실제 재귀함수가 쓰이는 곳에서는 매 호출시마다 입력값(파라메터)이 변한다. 저 링크를 클릭하는 건 입력값의 변화가 없는 호출이므로 이론상으로는 무한히 반복할 수 있다. 입력값의 변화가 없거나 입력값의 변화가 특정 패턴을 반복하게 되면 그 재귀함수는 영원히 반복되다가 콜스택 초과로 프로그램이 뻗어 버린다. 꼬리 재귀 최적화가 적용된 알고리즘은 그냥 영원히 돌면서 프로그램이 멈춰 버린다.

~~이렇게 된다.~~ 이래서 재귀함수는 종료조건이 반드시 있어야 한다.
따라서 재귀함수 설계 시에는 입력값이 종료 조건으로 수렴하는지를 꼭 검증해야 한다.

수학에서는 재귀함수라는 용어를 재귀를 포함함은 물론, 훨씬 더 광범위하게 정의하여 사용한다. 즉, 수학에서 모든 종류의 알고리즘은 재귀함수로 표현되며, 그렇기에 계산가능 함수(computable function)이라는 용어도 사용한다. 반복문(iteration, loop)과 변수를 이용하는 반복적 알고리즘은 재귀함수로 표현할 수 있고 그 역도 성립한다. 이에 영향을 받아 등장한것이 바로 LISP과 같은 함수형 언어인데, 모든 프로그램(즉, 알고리즘)을 함수로 표현할 수 있다는 것에 착안하여 만들어진 언어들이고, 이 언어들은 재귀를 밥먹듯이 사용한다.[2]

상술했듯 반복문으로 변수를 바꿔가는 형식의 명령형 계산은 항상 재귀적인 형식으로 똑같이 구현할 수 있으며 그 반대도 마찬가지지만[3], 현재 산업에서의 언어 패러다임은 대부분 명령형이기 때문에 대개 반복문으로 구현하는게 훨씬 익숙할 것이다. 무엇보다 함수가 호출될 때마다 호출 스택 메모리를 잡아먹는 경우 퍼포먼스 측면에서 반복문이 낫다. 다만 구현체에 꼬리재귀(Tail Recursion) 최적화가 되어있는 경우 꼬리재귀 요청이 스택에 걸리는 대신 이전 실행지점으로의 점프로 작동 하므로 실질적으로 루프문과 유의미한 성능 차이는 없게 된다.[4] 꼬리재귀 최적화의 경우 함수형 언어 구현체에는 필수적으로 들어가며, 명령형 언어 컴파일러에도 구현되어 있는 경우가 있다. C, C++의 경우 GCC, LLVM/ Clang, VC++ 등의 주요 컴파일러에는 다 구현되어 있기 때문에 안심하고 사용해도 된다.

대부분의 명령형 언어 구현체에서는 간단한 재귀함수를 몇 줄 차이뿐인 반복문으로 쓰는 것이 더 좋은 관계로[5] 절차적 언어에서의 재귀를 써야하는 경우는 매우 적다. 더불어 명령형 언어 사용자들이 재귀를 꺼리게 되는 추가적인 이유는 이게 반복을 하는 놈인지 아닌지 알기 어렵다는 점에 있다. 반복문이 대놓고 문장 한가운데서 '이 블록은 반복될 것임'하고 알려주는 것과 다르게 재귀는 별다른 표시없이 혼자 돌게 되므로 코드 내에서 가독성이 떨어지게 된다. 추가적으로, 흐름을 추적하기 어렵다는 이유도 한몫한다.

그리고 반복문의 경우는 For i=1..n처럼 유한히 반복된다는 사실을 명시할 수 있어, 코드만 보면 아무 증명 없이도 정지 문제를 쉽게 풀 수 있기 때문에 큰 도움이 된다. 이런 종류의 함수를 원시 재귀 함수라고 부르며 명령형 언어에서 원시 재귀 함수들처럼 반복의 상한을 계산할 수 있으면 재귀와 달리 반복문은 유한성을 명시할 수 있는 이점이 있다. 물론 While True 류의 반복문의 경우에는 적용되지 않는다.

그렇지만 명령형 언어에서도 재귀가 필요할 때가 있는데, 반복문으로 구현했다가는 코드가 심하게 복잡해지거나, 프로그래머가 만들다가 로직이 꼬여 안드로메다로 가는 상황이 발생하는 문제들도 있기 때문. 이 경우 재귀함수로 구현하는 것이 간단하고 훨씬 더 이해하기 쉬운 경우가 있다. 예를 들어 XML이나 JSON을 파싱한다거나 퀵 정렬을 만든다면 반복문보다 재귀를 쓰는 것이 더 쉽다. 이런 알고리즘을 생 루프문으로 처리하려면 스택을 따로 구현해야 한다.[6]

하지만 소프트웨어 위기와 병렬 컴퓨팅에 대두에 따라, 함수를 최대한 단순하게, 불변적으로 유지하는 것이 새로운 패러다임으로 떠올랐다. 수많은 함수형 언어들이 등장하는 것과 관련이 있다. 그에 따라 재귀함수 등의 함수형 사고를 통해 프로그래밍을 하는 것이 중요한 덕목 중 하나로 떠올랐다.

많은 함수형 언어 구현체에는 루프문이 없을 뿐더러 애초에 필요성도 별로 못 느낀다. 설령 언어에 루프가 있더라도 재귀적으로 구현했다간 코드가 심하게 복잡해지거나 안드로메다로 가는 특수한 상황이 아니면 거의 안쓴다. 그도 그럴 것이 루프문은 돌면서 변수를 변화시키고 루프가 끝나면 변화된 값을 얻어내는 목적이 있다. 그런데 함수형 언어에서는 일반적으로 변수가 없고 '정의'만이 있을 뿐이다. 정의된 값을 바꿀 수 없으니 바뀐 값을 입력으로 사용하는 호출 하나를 더 만들어내는 것이다. 예를 들어 리스트를 역순으로 바꾸는 함수 reverse는 이렇게 동작한다.

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

변수 index의 상태를 입력 리스트 s의 마지막 원소의 위치인 2로 설정하고, 매 반복마다 index를 하나씩 빼 가면서 해당 인덱스의 원소를 s에서 복사해 d에 넣는다. index가 0 미만이 되면 루프를 종료하고 d를 반환한다. 구현하기에 따라서 s와 d를 스택으로 간주해 pop-push하는 경우도 있지만 메모리가 극단적으로 모자라는 환경이 아닌 한 보통 저렇게 짠다.

극단적인 예시로, Haskell의 퀵 소트 알고리즘은 단 두 줄만으로 정의된다.

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

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

저 퀵 소트 알고리즘은 최적화가 되지 않았고(예를 들어 이미 정렬된 배열이나 역순 정렬에 대해 최악의 성능을 보인다) 꼬리재귀 최적화를 적용할 수 없기 때문에 성능은 꽤 나쁘게 나오지만 어쨌든 퀵 소트 알고리즘이 정의하는 그대로를 구현하고 있다. 단 두 줄의 정의문만으로!

상황이 이렇다보니 간단한 연산부터 일관되게 재귀로만 짜는 함수형 언어에 대한 절차적 언어 사용자들의 반응은 충격과 공포 그 자체. 더구나 함수형 언어 사용자는 변수 및 for-loop보다 재귀호출로 이루어진 것이 버그가 적고 가독성도 좋고(!) 로직이 훨씬 명확하다고 느낀다(!!). 오히려 재귀호출이 너무 당연한 개념이라 명령형 언어에서 재귀호출을 멀리하는 것을 이해하지 못한다.

이렇게 되는 이유 중의 하나는 프로그래밍을 생각하는 방식의 차이 때문이다. 명령형 언어에서 '상태와 그 상태의 변화의 반복'에 집중한다면, 함수형 언어에서는 '어떤 인자에 대응되는 값'이라는 관계, 즉 함수를 생각한다. 명령형 개념에서 재귀호출은 '자기 자신을 호출한다'라는 흐름 제어로 인식하는 반면, 함수형 패러다임에 익숙한 사람은 재귀호출은 마치 점화식처럼 자기 함수와의 값의 관계를 맺는 것이라고 생각한다.

이런 생각은 상태 변화를 생각하는 것과는 달리 관계 그 자체에 치중하여 코딩할 수 있게 한다. 또한, 이런 생각을 도와주는 게 함수형 언어에서 부수효과가 없다는 건데... 자세한 건 함수형 언어 참조. 아니면 LISP나 OCaml, Haskell 등의 함수형 언어를 공부하면서 뇌 개조(...)를 당해보면 된다.

위에는 함수형 언어를 사용할 시에 재귀함수를 반드시 작성해야 하는 것처럼 설명해 놨지만, 함수형 언어를 파고들다 보면 반복적인 처리를 요할 시에 재귀함수를 작성하지 않고, 재귀하는 부분만이 구현된 고차함수를 사용하는 것을 볼 수 있다. 가장 처음 배우는 예시가 fold/reduce 함수들이다. 실제로 fold만 가지고 상당히 재귀적인 호출을 요하는 많은 함수들을 정의할 수 있기 때문에, 함수형 언어에서 직접 재귀함수를 구현하는 경우는 매우 드물다.

더 나아가면, fold는 범주론의 catamorphism에 해당된다는 것을 알 수 있고, 이 외의 anamorphism, hylomorphism, metamorphism 등의 recursion scheme에 대해 알게 되면 모든 재귀적인 함수를 재귀를 사용하지 않고 정의하게 된다. (이정도 되면, 재귀함수는 goto와 비슷하다고 느껴져 코드에 넣는 것을 꺼리게 된다)

문서의 제목은 재귀함수이지만, 연결리스트나 트리와 같은 자료구조는 자신을 통해 정의된다는 점에서 재귀적인 자료구조이다. 명령형 언어중 객체 지향 언어일 경우, 재귀적인 자료구조를 통해 호출해서 간단하게 재귀함수를 활용할 수 있어 객체지향 언어의 생산성 향상에 일조한다. 함수형 프로그래밍을 깊게 공부했다면 이러한 자료구조도 Fix/Cofree와 같은 추상화를 통해 재귀없이 정의하게 된다.[7]

3. 예시

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

LISP 으로 작성된 피보나치 수열을 구하는 재귀함수. fibonacci-recursive 함수 내부에서 에서 자기 자신인 fibonacci-recursive에 n - 1, n - 2 를 인자로 넘겨서 다시 부르는 것을 볼 수 있다.

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).

Prolog로 작성된 Tail Recursion 형 피보나치 수열을 구하는 재귀함수. 위의 예제와 다르게 함수의 인자를 결과를 저장하는 변수처럼 사용하는 것을 볼 수 있으며, fib(N, R2, R1, RF) 함수의 정의 끝에서 자기 자신을 다시 부르는 것을 볼 수 있다. 많은 선언형, 논리형, 함수형 언어는 이러한 Tail-Recursion 형태의 재귀함수를 최적화하는 기능을 가지고 있다.

3.1. 자바스크립트

#!syntax javascript
function factorial(n) {

  if (n > 1) {

    return n* factorial(n-1);

    }

   return  1;
}

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

재귀함수로 구현된 자바스크립트 팩토리얼 연산

(결과값) 5! = 120

3.2. C++

#!syntax cpp

#include 

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);
}

c++로 구현된 재귀함수를 이용한 팩토리얼 연산, 비숫한 방법으로 C언어로도 가능하다.

(결과값) 입력된 n의 팩토리얼 값이 출력된다.

4. 기타

알고리즘 시간에 재귀적 사고 방식을 길러주려고 반복적 알고리즘을 재귀로 다시 구현하는 문제 등이 출제된다.

프로그래밍 언어를 배울 때 수학에서 재귀적으로 정의되어 반복문보다 가독성 좋게 재귀함수로 옮길 수 있는 팩토리얼, 하노이의 탑이나 피보나치 수열 등을 재귀함수로 구현하는 과제가 종종 출제된다. 팩토리얼, 재귀함수 등은 귀납적으로 정의되고, 이를 재귀함수로 구현하는 것은 몹시 당연한 사고방식이기 때문이다. 고등학교를 나온 대부분의 프로그래머는 이 귀납적으로 정의된 수열과 재귀함수 간의 관계를 이해하는데 문제가 없을 것이다. 한편 피보나치 수열의 경우에는 반복문으로 짠 경우와는 완전히 다른 시간복잡도를 가지기에 최적화의 예시로써도 언급되는 편.

여기서 더 나아가 병합 정렬, KMP 알고리즘, 위상 정렬, 이진 탐색 등 대부분의 알고리즘은 재귀적으로 파악하면 더욱 간명해지는 경우가 많다. 서울대 문병로 교수가 쓴 책의 이름은 아예 "재귀적, 귀납적 사고방식"을 가르친다고 대놓고 써있다. 단순히 기계적인 최적화 수준의 이야기를 넘어서, 알고리즘적 측면에서 보자면 재귀적 사고방식을 평소에 연습하는 것이 매우 중요하다. 재귀함수, 더 나아가 재귀적 사고 방식은 흔히 말하는 분할정복에 기초를 둔다. 어떤 리스트의 합을 구하는 경우를 생각해보자. 단순히 명령형 사고에 익숙해졌다면 이를 O(n)으로 구하고, 그 답에 만족했을 것이다. 하지만 이 문제는 재귀적으로 생각할 경우 O(log n)만에 해결할 수 있다. 이처럼 기계적 수준의 최적화가 아니라, 더 높은 수준의 생산성과 효율을 추구한다면 평소에 재귀적으로 사고하는 습관을 들여야 한다.

또한 Big-O를 계산하거나 이해하는 데 큰 도움을 주기 때문에 자료구조 초반부(리스트 개념을 배우기 전)에 다뤄진다. 함수가 재귀적으로 짜여 있는 경우 점화식 형태로 연산의 횟수를 셀 수 있기 때문에 Big-O 계산이나 증명을 쉽게 할 수 있다.

간혹 명령형 언어에서 재귀함수를 퍼포먼스가 떨어진다고 안 쓰는 게 좋다고 가르치기도 한다.[8] 그러나 꼬리재귀 호출을 할 수 없으면서[9] 스택 깊이 이상[10]을 뚫어버리는 경우가 아니면 굳이 거부할 필요는 없다. 오히려 의미상 더 명료하다면 신용하는 게 나을 수 있다. 요즘 컴파일러들은 아주 똑똑해서 재귀 호출 최적화[11]를 잘한다. 꼬리 재귀가 아니더라도 실행 순서를 조정한다든지 함수 몇 개를 합친다든지 해서 최적화가 가능하면 그렇게 한다.[12] 실제로 STL 알고리즘 구현체도 내부적으로 재귀호출을 쓰는 경우가 많고 Mac의 C언어 qsort 함수 구현체도 재귀호출을 사용한다. #

JSON, XML의 문법 자체도 재귀적이기 때문에 Recursive Descent Parsing 기법처럼 재귀를 사용해 파싱하는 것이 가장 직관적이다. 물론 재귀를 사용하지 않는 파싱 기법들도 있지만 전공책을 뒤져봐야 재대로 이해할 수 있을 것이다.

그러나 아무리 꼬리재귀 최적화가 완벽히 되더라도 정말 특수한 경우가 아니라면 콜스택 등의 오버헤드 문제가 아예 없어지는 것은 또 아니고, 캐쉬 지역성 문제[13]로 인해 성능이 떨어지는 것은 맞다. 단지 그 차이가 유의미하지 않을 뿐.

이런 식의 유연성과 성능의 trade-off는 프로그래밍에서는 일상이고, 개발 목적에 맞는가, 허용 범위 내인가가 더 중요하다. 그렇지만 다른 걸 다 떠나서 재귀를 재대로 쓰는 알고리즘들은 전공책이나 논문에서 보는 알고리즘들일 경우니, 수학이나 컴퓨터 과학에 지식이 빠삭한 경우가 아니라면 함부러 루프문으로 바꿀 경우 버그만 발생시킬 수 있기 때문에 여러분이 저런 식의 마이크로튜닝을 못한다고 업계에서 비난받을 이유는 거의 없다고 볼 수 있다.

재귀 함수는 치환이 무한히 이루어지기 때문에 인라인 함수로 사용할 수 없다.

Python은 함수 깊이 제한이 기본 1000으로 되어 있어서, 대충 995회 쯤 재귀를 하면 뻗어버린다. 또한 꼬리재귀 최적화 역시 지원하지 않는다. sys.setrecursionlimit을 수정해 주면 1000 이상으로 늘릴 수 있으나, 그냥 많은 재귀를 해야 할 필요가 있으면 이 외에 꼬리재귀를 지원하는 언어를 사용하라. 다른 방법으로는 사용자 지정 예외 처리와 데코레이터를 사용하여 꼬리 재귀의 재귀 한계를 뚫는 방법이 있다. 또한 조금 더 수정해서 아예 데코레이터만 붙이면 꼬리 재귀의 한계를 없애주는 버전도 있다!(Python 2.4)

재귀함수의 설명 상황을 아래처럼 비유하곤 한다.

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이 세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네.
그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이 세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네.
그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이 세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네.
그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이 세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네.
그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
"재귀함수가 뭔가요?
"잘 들어보게. 옛날옛날..."

세상에서 제일 위험한 꿈은 꿈을 꾸는 꿈이라 하였다. 영화 인셉션에서 이 소재를 다루고 있다.[14] 또한 프랙탈이라는 특수한 도형은 패턴이 재귀적으로 반복되기 때문에, 넓이(또는 부피)는 유한하지만 길이(또는 겉넓이)는 무한하다는 괴상한 성질을 갖고 있다. 프랙털 도형은 1차원, 2차원 같은 정수 차원이 아니라 1.5차원 같은 실수 차원에 존재한다.

0으로 나누기 역시나 구형 계산기에서는 이 일이 일어난다.

5. 재귀적 정의

재귀적 정의는 어떤 것을 정의(definition)할 때 자기 자신을 재사용하여 정의해야 하는 원시적(또는 근본적인)인 정의 단계를 가리킨다. 순환 정의라고도 한다. 모든 정의는 언젠가는 재귀적 정의로 귀결된다. 예를 들어 국어사전의 단어 정의가 대표적이다. 국어사전은 언어의 설명이 목적이지 모든 언어의 정의를 하는 것이 목적이 아니므로 어떤 단어의 모든 정의를 살펴보면 순환 참조가 되거나 재귀적 정의로 귀결된다.

6. 관련 문서

재귀함수

[1] 링크 오류가 아니다! 구글도 비슷한 예를 들고 있다. recursion으로 검색해보자. 구글의 센스를 엿볼 수 있다. [2] 보통 ML계열 같은 하이브리드 함수형 언어가 아니면 반복문 자체가 없거나, 있더라도 재귀로 구현되어 있다. [3] 그러나 난이도는 동일하지 않다. 트리 자료구조의 전위, 중위, 후위 순회(preorder, inorder, postorder traversal)를 재귀가 아니라 루프로 짜려면 머리 좀 싸매야 할 것이다. 하노이의 탑도 마찬가지. [4] 물론 구현체에 꼬리재귀 최적화가 없거나 재귀함수가 꼬리재귀할 수 없다면, 루프문이 무조건 빠르다. [5] 주요 구현체 중 꼬리재귀 최적화가 없는 경우가 있기 때문이다. 대표적으로 Java는 꼬리재귀 최적화가 없다. JVM에서 동작하는 다른 언어들 중에는 꼬리재귀 최적화가 구현되어 있는 경우가 많다. [6] 구현 난이도는 올라갈 수 있으나, 스레드 시작시에 크기가 결정되는 함수 스택을 사용할 때보다 동적 할당을 사용할 수 있는 사용자 정의 스택을 활용할 때 좀더 유연한 구현이 가능하다. [7] 더 자세히 알고 싶으면, Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire를 읽어볼 것. [8] 그와는 별개로 학생 입장에서 크게 느끼는 케이스가 상술한 피보나치 수열이다. 반복문으로 짰을 시 [math(O(n))]의 시간복잡도를 보이는데 재귀 호출로 짜면 [math(O(2^n))]의 시간 복잡도를 보이기 때문. 다만 알고리즘을 만드는 과정에서 시간복잡도가 다르게 나오는 그 자체로 일단은 특이케이스. [9] 위에도 언급하고 있지만 꼬리재귀가 가능한 경우 루프와 마찬가지로 그냥 점프한다. [10] C/C++의 경우엔 함수를 호출할 때 리턴할 주소, 호출할 함수에 전달할 매개변수, 현재 쓰고 있는 지역 변수 등의 값을 스택에 저장한다. 요즘엔 스택 영역을 크게 잡아줄 수 있긴 하지만 계속 꼬리에 꼬리를 물며 재귀함수를 호출하면 결국엔 스택 영역이 꽉 차서 스택 오버플로가 발생한다. [11] C의 경우엔 최적화가 안 되는 경우에는 jmp label; 로 루프하던 루프문이 call label; (push eip; jmp label;) 로 꽉 들어찰 뿐만 아니라 재귀문에서 나올 때 ret 4;(mov eax, esp; add esp, 4; jmp eax;)를 하게 된다. 간단하게 1번 할 것을 5번으로 불려버리는(...) [12] Java 제외. 자바 가상 머신의 한계로 꼬리재귀 최적화가 불가능하다. 하지만 같은 JVM 상 언어지만 Scala의 경우 @tailrec 어노테이션을 사용해 꼬리재귀 최적화를 실시한다. [13] 반복문으로 짜면 가능했을 루프 펼치기, 캐쉬 라인 최적화, 프리패칭, 투기적 실행 등의 고급 기법을 쓰기 힘들다. 완전히 안 되는 건 아니지만... [14] 오죽했으면 재귀적 구조가 나오면 -셉션이라는 접미사를 붙이는 드립이 성행했을 정도. 이런 재귀적 구조는 크리스토퍼 놀란이 즐겨 쓰는 소재이다.

재귀함수

1. 개요

2. 설명

3. 예시

3.1. 자바스크립트

3.2. C++

4. 기타

5. 재귀적 정의

6. 관련 문서

분류