문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 재귀함수 (문단 편집) == 기타 == [[알고리즘]] 시간에 재귀적 사고 방식을 길러주려고 반복적 알고리즘을 재귀로 다시 구현하는 문제 등이 출제된다. [[프로그래밍 언어]]를 배울 때 수학에서 재귀적으로 정의되어 반복문보다 가독성 좋게 재귀함수로 옮길 수 있는 [[팩토리얼]], [[하노이의 탑]]이나 [[피보나치 수열]] 등을 재귀함수로 구현하는 과제가 종종 출제된다. 팩토리얼, 재귀함수 등은 귀납적으로 정의되고, 이를 재귀함수로 구현하는 것은 몹시 당연한 사고방식이기 때문이다. 고등학교를 나온 대부분의 프로그래머는 이 귀납적으로 정의된 수열과 재귀함수 간의 관계를 이해하는데 문제가 없을 것이다. 여기서 더 나아가 [[병합 정렬]], [[문자열 알고리즘#KMP|KMP 알고리즘]], [[위상 정렬]], [[이진 탐색]] 등 대부분의 알고리즘은 재귀적으로 파악하면 더욱 간명해지는 경우가 많다. 서울대 문병로 교수가 쓴 책의 이름은 아예 "재귀적, 귀납적 사고방식"을 가르친다고 대놓고 써있다. 단순히 기계적인 최적화 수준의 이야기를 넘어서, 알고리즘적 측면에서 보자면 재귀적 사고방식을 평소에 연습하는 것이 매우 중요하다. 재귀함수, 더 나아가 재귀적 사고 방식은 흔히 말하는 분할정복에 기초를 둔다. 어떤 리스트의 합을 구하는 경우를 생각해보자. 단순히 명령형 사고에 익숙해졌다면 이를 O(n)으로 구하고, 그 답에 만족했을 것이다. 하지만 이 문제는 재귀적으로 생각할 경우 O(log n)만에 해결할 수 있다. 이처럼 기계적 수준의 최적화가 아니라, 더 높은 수준의 생산성과 효율을 추구한다면 평소에 재귀적으로 사고하는 습관을 들여야 한다. 또한 [[점근 표기법|Big-O]]를 계산하거나 이해하는 데 큰 도움을 주기 때문에 자료구조 초반부(리스트 개념을 배우기 전)에 다뤄진다. 함수가 재귀적으로 짜여 있는 경우 점화식 형태로 연산의 횟수를 셀 수 있기 때문에 Big-O 계산이나 증명을 쉽게 할 수 있다. 간혹 명령형 언어에서 재귀함수를 퍼포먼스가 떨어진다고 안 쓰는 게 좋다고 가르치기도 한다. 그러나 꼬리재귀 호출을 할 수 없으면서[* 위에도 언급하고 있지만 꼬리재귀가 가능한 경우 루프와 마찬가지로 그냥 점프한다.] 스택 깊이 이상[* C/C++의 경우엔 함수를 호출할 때 리턴할 주소, 호출할 함수에 전달할 매개변수, 현재 쓰고 있는 지역 변수 등의 값을 스택에 저장한다. 요즘엔 스택 영역을 크게 잡아줄 수 있긴 하지만 계속 꼬리에 꼬리를 물며 재귀함수를 호출하면 결국엔 스택 영역이 꽉 차서 스택 [[오버플로]]가 발생한다.]을 뚫어버리는 경우가 아니면 굳이 거부할 필요는 없다. 오히려 의미상 더 명료하다면 신용하는 게 나을 수 있다. 요즘 [[컴파일러]]들은 아주 똑똑해서 재귀 호출 최적화[* C의 경우엔 최적화가 안 되는 경우에는 {{{jmp label;}}} 로 루프하던 루프문이 {{{call label; (push eip; jmp label;)}}} 로 꽉 들어찰 뿐만 아니라 재귀문에서 나올 때 {{{ret 4;(mov eax, esp; add esp, 4; jmp eax;)}}}를 하게 된다. 간단하게 1번 할 것을 5번으로 불려버리는(...)]를 잘한다. 꼬리 재귀가 아니더라도 실행 순서를 조정한다든지 함수 몇 개를 합친다든지 해서 최적화가 가능하면 그렇게 한다.[* [[Java]] 제외. [[자바 가상 머신]]의 한계로 꼬리재귀 최적화가 불가능하다. 하지만 같은 JVM 상 언어지만 Scala의 경우 @tailrec 어노테이션을 사용해 꼬리재귀 최적화를 실시한다.] 실제로 STL 알고리즘 구현체도 내부적으로 재귀호출을 쓰는 경우가 많고 [[Mac(컴퓨터)|Mac]]의 C언어 qsort 함수 구현체도 재귀호출을 사용한다. [[http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c|#]] JSON, XML의 문법 자체도 재귀적이기 때문에 Recursive Descent Parsing 기법처럼 재귀를 사용해 파싱하는 것이 가장 직관적이다. 물론 재귀를 사용하지 않는 파싱 기법들도 있지만 [[전공책]]을 뒤져봐야 재대로 이해할 수 있을 것이다. 그러나 아무리 꼬리재귀 최적화가 완벽히 되더라도 정말 특수한 경우가 아니라면 콜스택 등의 [[오버헤드]] 문제가 아예 없어지는 것은 또 아니고, 캐쉬 지역성 문제[* 반복문으로 짜면 가능했을 루프 펼치기, 캐쉬 라인 최적화, 프리패칭, 투기적 실행 등의 고급 기법을 쓰기 힘들다. 완전히 안 되는 건 아니지만...]로 인해 성능이 떨어지는 것은 맞다. 단지 그 차이가 유의미하지 않을 뿐. 이런 식의 유연성과 성능의 trade-off는 프로그래밍에서는 일상이고, 개발 목적에 맞는가, 허용 범위 내인가가 더 중요하다. 그렇지만 다른 걸 다 떠나서 재귀를 재대로 쓰는 알고리즘들은 [[전공책]]이나 [[논문]]에서 보는 알고리즘들일 경우니, 수학이나 컴퓨터 과학에 지식이 빠삭한 경우가 아니라면 함부러 루프문으로 바꿀 경우 버그만 발생시킬 수 있기 때문에 여러분이 저런 식의 마이크로튜닝을 못한다고 업계에서 비난받을 이유는 거의 없다고 볼 수 있다. 재귀 함수는 [[치환]]이 무한히 이루어지기 때문에 [[인라인 함수]]로 사용할 수 없다. [[Python]]은 함수 깊이 제한이 기본 1000으로 되어 있어서, 대충 995회 쯤 재귀를 하면 뻗어버린다. 또한 꼬리재귀 최적화 역시 지원하지 않는다. {{{sys.setrecursionlimit}}}을 수정해 주면 1000 이상으로 늘릴 수 있으나, 그냥 많은 재귀를 해야 할 필요가 있으면 이 외에 꼬리재귀를 지원하는 언어를 사용하라. 다른 방법으로는 사용자 지정 예외 처리와 데코레이터를 사용하여 꼬리 재귀의 재귀 한계를 뚫는 방법이 [[https://chrispenner.ca/posts/python-tail-recursion|있다.]] 또한 조금 더 수정해서 아예 데코레이터만 붙이면 꼬리 재귀의 한계를 없애주는 버전도 [[http://code.activestate.com/recipes/474088-tail-call-optimization-decorator/|있다!(Python 2.4)]] 재귀함수의 설명 상황을 아래처럼 비유하곤 한다. >어느 한 [[컴퓨터공학과]] 학생이 유명한 교수님을 찾아가 물었다. >"재귀함수가 뭔가요?" >"잘 들어보게. 옛날옛날 한 산 꼭대기에 이 세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. >그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어. >>'''"재귀함수가 뭔가요?"''' >>"잘 들어보게. 옛날옛날 한 산 꼭대기에 이 세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. >>그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어. >>>"재귀함수가 뭔가요?" >>>"잘 들어보게. 옛날옛날 한 산 꼭대기에 이 세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. >>>그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어." >>>>"재귀함수가 뭔가요?" >>>>"잘 들어보게. 옛날옛날 한 산 꼭대기에 이 세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. >>>>그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어." >>>>>"재귀함수가 뭔가요? >>>>>"잘 들어보게. 옛날옛날..." 세상에서 제일 위험한 [[꿈]]은 '''[[꿈속의 꿈|꿈을 꾸는 꿈]]'''이라 하였다. 영화 [[인셉션]]에서 이 소재를 다루고 있다.[* 오죽했으면 재귀적 구조가 나오면 -셉션이라는 [[접미사]]를 붙이는 드립이 성행했을 정도. 이런 재귀적 구조는 [[크리스토퍼 놀란]]이 즐겨 쓰는 소재이다.] 또한 [[프랙탈 이론|프랙탈]]이라는 특수한 도형은 패턴이 재귀적으로 반복되기 때문에, 넓이(또는 부피)는 유한하지만 길이(또는 겉넓이)는 [[무한]]하다는 괴상한 성질을 갖고 있다. [[http://navercast.naver.com/contents.nhn?rid=22&contents_id=1273|프랙털 도형]]은 1차원, 2차원 같은 정수 차원이 아니라 1.5차원 같은 실수 차원에 존재한다. [[0으로 나누기]] 역시나 구형 계산기에서는 이 일이 일어난다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기