재귀함수

리듬게임 수록곡에 대해서는 リカーシブ・ファンクション 문서를 참조하십시오.

再歸函數
recursive function
recursion(재귀)

1 개요

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

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

이 교수님 은근슬쩍 자기 자신을 선인에 비유했다
들여쓰기는 의도된거다

2 설명

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

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

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

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

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

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

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

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

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

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

반면에 함수형 언어로 가면 상황은 180도 달라지는데, 많은 함수형 언어 구현체에는 루프문이 없을 뿐더러 애초에 필요성도 별로 못 느낀다. 설령 언어에 루프가 있더라도 재귀적으로 구현했다간 코드가 심하게 복잡해지거나 안드로메다로 가는 이거 어디서 많이 본 문장인데 특수한 상황이 아니면 거의 안쓴다. 그도 그럴 것이 루프문은 돌면서 변수를 변화시키고 루프가 끝나면 변화된 값을 얻어내는 목적이 있다. 그런데 함수형 언어에서는 일반적으로 변수가 없고 '정의'만이 있을 뿐이다. 정의된 값을 바꿀 수 없으니 바뀐 값을 입력으로 사용하는 호출 하나를 더 만들어내는 것이다. 예를 들어 리스트를 역순으로 바꾸는 함수 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하는 경우도 있지만 메모리가 극단적으로 모자라는 환경이 아닌 한 보통 저렇게 짠다.

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

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

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

3 예시

(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 형태의 재귀함수를 최적화하는 기능을 가지고 있다.

4 기타

알고리즘 시간에 가끔 재귀 관계적 사고 방식을 길러주려고 일부러 반복문 포함된 알고리즘을 재귀식으로 변환하라는 문제가 나오기도 한다.

프로그래밍 언어를 배울 때 수학에서 재귀적으로 정의되어 반복문보다 가독성 좋게 재귀함수로 옮길 수 있는 팩토리얼, 하노이의 탑이나 피보나치 수열등을 재귀함수로 구현하는 과제가 종종 출제된다.피보나치 수열은 반복문이 더 간단해 보이는 것을 재귀로 짜라고 해놓고 비효율적이라고 다시 반복문으로 짜라고 가르친다 다만 재귀함수를 아직 잘 이해하지 못한 뉴비들이 구현하면 99.9% 무한루프에 빠진다(…). 재귀 함수의 무한루프에서 벗어나고 싶으면 함수를 종료할 조건을 넣어 줘야 한다. 참고로 필수다.프로그래밍 좀 해본 뉴비나 무한루프에 빠지고 대부분은 우선 문법오류를 접하겠지만. 이런 무한 루프에 빠지게 되는 경우를 점화식에 빗대어 생각해보면 관계식은 있는데 초항은 없는 꼴인거다.

간혹 명령형 언어에서 재귀함수를 퍼포먼스가 떨어진다고 안 쓰는 게 좋다고 가르치기도 한다. 그러나 꼬리재귀 호출을 할 수 없으면서 스택 깊이 이상을 뚫어버리는 경우가 아니면 의도적인 알러지 반응을 일으킬 필요는 없다. 오히려 의미상 더 명료하다면 사용하는게 좋다. 요즘 컴파일러들은 아주 똑똑해서 재귀 호출 최적화를 잘한다. 꼬리 재귀가 아니더라도 실행 순서를 조정한다던지 함수 몇 개를 합친다던지 해서 최적화가 가능하면 그렇게 한다. 실제로 STL 알고리즘 구현체도 내부적으로 재귀호출을 쓰는 경우가 많고 Mac의 C언어 qsort 함수 구현체도 재귀호출을 사용한다. # 또한 수많은 프로그래밍 언어 및 JSON, XML 등의 파서는 Descent Recursive Parser인데 이 파서는 모두 재귀호출을 이용한다.

파이썬은 함수 깊이 제한이 기본 1000으로 되어 있어서, 대충 995회 쯤 재귀를 하면 뻗어버린다. 또한 꼬리재귀최적화 역시 지원하지 않는다. sys.setrecursionlimit 을 수정해 주면 1000 이상으로 늘릴 수 있으나, 그냥 많은 재귀를 해야 할 필요가 있으면, C로 짜라.