꼬리 재귀(Tail Recursion)은 우회법(workaround)일 뿐...
fupfin
몇몇 분과 얘기를 나눈 내용인데요.
꼬리재귀(Tail Recursion)은 특정 함수가 직,간접적으로 자신을 꼬리호출
(Tail Call)함으로써, 재귀를 하면서도 스텍프레임을 재사용할 때를 부르는
말인데요. 함수형 프로그래밍을 배우는 사람들에게 뭔가 넘어서야 할 것 같은
고급 기술인 것 처럼 취급되고 있죠. 그런데, 일반 재귀호출을 컴파일러가 자
동으로 꼬리재귀로 최적하는 상황이라면 모를까, 프로그래머가 수작업으로 꼬
리재귀가 일어나도록 코드를 작성하는 경우라면 제가 보기엔 함수형 언어의
단점을을 드러내는 부분 아닌가 싶습니다.
제 말은, 함수형으로 추상화한 코드가 있을 때, 호출이 반복될 수록 스텍이
깊어져 문제가 된다면, 이를 선형으로 처리되도록 알고리즘을 바꿔 스텍프레
임을 재사용함으로써 문제를 해결하는 게 꼬리재귀인데요. 이 알고리듬 변환
작업이 재귀호출로 작성된 알고리듬을 절차형 언어에서 반복문으로 처리되도
록 변환할 때와 동일하다는 겁니다.
결국 꼬리 재귀는 절차형 언어의 반복문(while, for, do...while,
repeat...until 등)을 함수형에서 표현하는 다른 방법일 뿐이란 생각이구요.
구조를 추적하기 힘들게 만드는 데 비해서 추상화 효과는 별로 없는 걸로 보
입니다.
얼마 전에는 꼬리재귀로 작성된 코드를 다 반복 구문으로 바꿔본 일이 있는데
코드 블럭의 크기가 크지만 많다면 훨씬 코드 흐름을 파악하기 좋더군요.
강한 반론 기대하겠습니다. ^^
blueiur
--
Google 그룹스 '라 스칼라 코딩단' 그룹에 가입했으므로 본 메일이 전송되었습니다.
이 그룹에 게시하려면 scala...@googlegroups.com(으)로 이메일을 보내세요.
그룹에서 탈퇴하려면 scala-korea+unsubscribe@googlegroups.com로 이메일을 보내주세요.
더 많은 옵션을 보려면 https://groups.google.com/groups/opt_out을(를) 방문하세요.
fupfin
>
> 하지만 알고리즘을 세우는 과정에서 재귀와 루프는 생각하는 방식이 다르게
> 나타나는 것 같습니다.
> 재귀 -> 꼬리재귀는 쉽게 변환이 가능하지만 재귀 -> 루프는 생각만큼 쉽게
> 변경되지 않더라고요(제 경우에는)
다고 생각되는데요. 혹시 쉽지 않다고 하신 이유가 재귀까지 루프로 바꾸는
것을 포함해서 말씀하신 건가요? 저는 일반 함수 호출과 재귀는 그대로 놔두
고 꼬리재귀만 루프로 바꾸는 상황을 말씀드린 겁니다.
blueiur
일반적인 재귀까지 포함해서 적은 글입니다.
일반적인 꼬리재귀는 항상 루프로 바로 변경이 가능한지에 대해서 조금 더 생각을 해 봐야겠네요 :)
답변 감사합니다.
Hyunsok Oh
꼬리재귀는 항상 루프로 변경 가능합니다.(정확히 말하면 루프가 아니라 goto입니다)
C스타일로 한글로 쓰자면..
리턴형 함수(인자형1 인자1, 인자형2 인자2...인자형n 인자n)
{
명령어1;
명령어2;
return 함수(새인자1, 새인자2,... 새인자n);
}
이런 형태의 꼬리재귀는 항상...
리턴형 함수(인자형1 인자1, 인자형2 인자2...인자형n 인자n)
{
RESTART:
명령어1;
return 무언가다른결과값;
명령어2;
....
{
인자1 = 새인자1;
인자2 = 새인자2;
...
인자n = 새인자n;
goto RESTART;
}
....
....
명령어n
}
가 됩니다. 증명을 하자면 아마도 return되는 경로를 가지고 수학적 귀납법+rewriting rule을 쓰면 될것 같습니다.
이게 근데 일반적인 재귀를 루프로 바꾸려면 데이터를 저장(스택프레임 저장)해야 하므로, 별도의 데이터 구조를 넣어야 할겁니다.
(당연히 문제에 따라서는 쉽게 되는것도 있고, 최악의 경우에는 스택을 에뮬레이션 해야겠죠... 그러면 굳이 이터레이션을 택할
이유가 없습니다만..)
게다가 재귀->꼬리재귀가 쉽게 된다면, 꼬리재귀->루프 변환을 그 다음에 하면 됩니다.
2012/10/2 blueiur <blu...@gmail.com>:
>
> 일반적인 재귀까지 포함해서 적은 글입니다.
>
> 일반적인 꼬리재귀는 항상 루프로 바로 변경이 가능한지에 대해서 조금 더 생각을 해 봐야겠네요 :)
>
> 답변 감사합니다.
>
>
> 2012. 10. 2. 오후 6:02에 "fupfin" <fup...@gmail.com>님이 작성:
>
>> 오호! 빠른 반응! 반갑습니다. ^^
>>
>>>
>>> 하지만 알고리즘을 세우는 과정에서 재귀와 루프는 생각하는 방식이 다르게 나타나는 것 같습니다.
>>> 재귀 -> 꼬리재귀는 쉽게 변환이 가능하지만 재귀 -> 루프는 생각만큼 쉽게 변경되지 않더라고요(제 경우에는)
>>
>>
>> 이 부분이 무척 궁금하네요. 저는 꼬리 재귀는 거의 즉각 루프로 바꿀 수 있 다고 생각되는데요. 혹시 쉽지 않다고 하신 이유가
>> 재귀까지 루프로 바꾸는 것을 포함해서 말씀하신 건가요? 저는 일반 함수 호출과 재귀는 그대로 놔두 고 꼬리재귀만 루프로 바꾸는 상황을
>> 말씀드린 겁니다.
>>
>> --
>> Google 그룹스 '라 스칼라 코딩단' 그룹에 가입했으므로 본 메일이 전송되었습니다.
>> 이 그룹에 게시하려면 scala...@googlegroups.com(으)로 이메일을 보내세요.
>> 그룹에서 탈퇴하려면 scala-korea...@googlegroups.com로 이메일을 보내주세요.
>> 더 많은 옵션을 보려면 https://groups.google.com/groups/opt_out을(를) 방문하세요.
>>
>>
> --
> Google 그룹스 '라 스칼라 코딩단' 그룹에 가입했으므로 본 메일이 전송되었습니다.
> 이 그룹에 게시하려면 scala...@googlegroups.com(으)로 이메일을 보내세요.
> 그룹에서 탈퇴하려면 scala-korea...@googlegroups.com로 이메일을 보내주세요.
Hyunsok Oh
1) 꼬리재귀 vs 꼬리재귀 최적화
꼬리재귀 함수는 본질적으로 루프와 같습니다. 사실은 표현만 재귀적 함수로 되어있을 뿐이지, 계산을 처리해 나가는 과정 자체는
선형적입니다. 하지만, 꼬리재귀 최적화가 없다면(영어로는 tail recursion elimination/tail call
elimination이라 합니다), 꼬리재귀 자체의 이점이 없습니다.
예를 들어 gcd 함수를 봅시다. 오덕스키선생님이 설명해 준 프로세스를 생각해 보지요.
다시쓰기 규칙으로 잘 설명해 주셨지만, 다 빼고 함수 호출만 살펴봅시다.
gcd(14, 21)
->> gcd(21, 14)
->> gcd(14, 7)
->> gcd(7, 0)
이 시점(gcd(7,0)을 호출하는 시점)에 스택에 위와 같이 4단계 스택프레임이 쌓여 있습니다.
이제 gcd(7,0)의 if문에서 0이 반환되면, 이 4단계 프레임을 차례로 pop해야 합니다.
즉, 꼬리재귀최적화가 없다면, 어차피 스택은 그대로 사용하고, 함수에서 리턴한 다음 바로 다시 리턴을 또 해야 한다는
것입니다. 리턴한 다음 바로 리턴할꺼라면 함수 호출로 처리하지 말고 점프로 바꾸되, 스택을 직접 업데이트해서 메모리도 아끼고,
반환 횟수도 줄이자는게 꼬리재귀 최적화의 목적입니다.
따라서, 계산 프로세스/복잡도 관점에서의 꼬리재귀와 이를 실제 구현할 때 최적화 관점에서의 꼬리재귀를 혼동하면 안될 것
같습니다. 그리고 gcc/g++이나 MS VC등의 컴파일러 최적화에도 꼬리재귀 함수의 최적화는 들어가 있습니다. 단순
꼬리재귀를 최적화하는 것은 쉬워보이지만, 좀 더 생각해보면 이 또한 문제가 여럿 있습니다. C/C++의 경우 중간중간 생기는
객체들의 소멸자 문제(함수 리턴시 호출해야 하는데, 이게 어느 시점이 되야 할까요?), 함수언어의 경우에는 패턴매치와 연관되서
꼬리재귀가 꼬리재귀가 아닌 경우 등등이 있습니다.
2) 재귀->꼬리재귀 변환
재귀를 꼬리재귀로 변환하면 몇가지 잇점이 있습니다.
가. 꼬리재귀 최적화를 통해 메모리와 시간상 이익을 얻을 수 있습니다.
나. 명시적으로 어떤 데이터가 호출과 호출 사이에 유지되어야 하는지를 알 수 있습니다. 예를 들어 fact()와 이의
꼬리재귀 버전 factIter()를 보면 중간계산결과를 함수 인자로 계속 넘겨줍니다. 만약 fact를 루프와 변수를 사용해
만든다면 당연히 결과값을 저장하는 변수를 하나 둘텐데, 저 인자가 바로 동일한 역할을 합니다. 만약 스택프레임을 재활용한다면,
꼬리재귀호출에서 인자를 호출하는 것은 스택프레임상의 특정 위치를 업데이트 하는 것으로 바뀌게 되지요.
하지만, 잘 보시면 가, 나 모두 생각하는 방법 측면에서 얻는 이익이 아니라 실행측면(컴파일러/컴퓨터 관점)에서 얻는 이익이란
것을 알 수 있습니다.
따라서 재귀->꼬리재귀 변환을 자동으로 해주되, 개발자는 이를 신경쓰지 않고 그냥 로직을 기술하면 되도록 하는것이 가장
좋을겁니다. 당연히 많은 사람이 이를 연구해왔고, 기계적인 번역 방법도 여럿 있습니다. 재귀를 꼬리재귀로 변환해서 최적화해주는
컴파일러로는 GHC(하스켈)가 있습니다.
이런저런 관련 자료가 있지만, 일반 스칼라 개발자 입장에선 머리만 복잡해질듯 하여 생략합니다.
blueiur
결국 꼬리재귀는 단순 최적화 관점 에서만 의미가 있는거군요. 좋은 글 감사합니다.
fupfin
한가지만 더, 제가 정말 토론하고 싶은 건데요.
제가 함수형 언어를 잘 모르는 편이라 맞는 말인지 모르겠지만, 하스켈이야
원래 반복문이 없으니 [물론, 따로 High Order Function(이걸 우리 말로 뭐라
고 하나요?)을 사용해서 반복문을 구현하기는 했지만] 꼬리 재귀로 선형적인
반복 구문을 표현한다고 하더라도, 스칼라는 (while, for 같은) 절차적 언어
의 반복 구문이 이미 있으니 굳이 선형적 반복을 꼬리재귀로 표현할 필요 없
이 반복문으로 코드를 표현해도 되지 않을까 싶습니다. (이 토론의 제목을 다
시 읽어 주시면... ^^)
물론 재귀적 표현을 사용하면 코드가 간결해지는 효과가 있기는 하지만 그만
큼 반복의 의미가 한단계 가리기 때문에 명시성이 떨어져 그리 큰 장점이 있
다고 볼 수 만은 없지 싶습니다.
아니면 @tailrec이 붙은 재귀는 관례적으로 선형적 반복이라고 읽는 쪽이 나
을까요? ㅎㅎ
논외로, @tailrec의 단점이 하나 있습니다. 특정 함수를 상황에 따라 꼬리재
귀로 부르기도 하고 일반 재귀로 부르기도 해야 할 때가 있는데, 이 때
@tailrec을 쓰면 컴파일 오류가 뜨더군요. @tailrec을 메서드 선언 위가 아니
라 호출하는 명령에 붙이도록 하면 좋을 것 같다는 생각이...
12. 10. 3. 오전 10:23, Hyunsok Oh 쓴 글:
윤재진
--
Google 그룹스 '라 스칼라 코딩단' 그룹에 가입했으므로 본 메일이 전송되었습니다.
이 그룹에 게시하려면 scala...@googlegroups.com(으)로 이메일을 보내세요.
그룹에서 탈퇴하려면 scala-korea+unsubscribe@googlegroups.com로 이메일을 보내주세요.
블로그 : http://spyrogira256.blogspot.com
Google Talk. spyrogira256@gmail.com
NateOn. anjff...@lycos.co.kr
Mobile. 010-9747-8761
========================================
fupfin
12. 10. 5. 오전 12:06, 윤재진 쓴 글:
while 같은걸로 대부분은 처리는 가능하지만.
트리 구조에서 밑에서 부터 거꾸로 올라가는 예제나 이런 경우는 위에서 부터 밑으로 찾아가는 트리구조 같은 경우에
재귀로 찾아가는게 좋지 않을까 싶습니다.
재귀적인 사상으로 문제를 풀면 쉽게 풀리는게
조합문제도 재귀적인 생각을 가지고 있다.
[A B C D] 란 문자가 있을때 이걸..
A B C D AB AC AD BC ....
이런걸 풀때는 while , for 이런걸로 풀게 되면 복잡도가 더 높아지는데.
재귀적으로 풀면 더 쉽게 풀렸던거 같습니다.
scala는 문법만 공부해보고 잘 안해봐서 ㅡㅡ;;
다른 Functional 기능 제공하는 언어들을 보면 (Erlang, Lisp, Scheme) 보통은 재귀로 다 문제가 해결되니 특별히 while, for 문법등이 없거나. macro로 직접 만들어서(Lisp)로 제공하거나 직접 만들어서 (Lisp) 사용하게 하는거 같습니다.
그러니깐 직접 만들수 있으니 특별히 따로 제공을 안하는거 같습니다. ㅡㅡ;;
scala에서는 최적화된 기능이 있으니 제공을 하는것도 있는거 같습니다.
그냥 보다가 허접하게 생각이 들어서 적어봤습니다.
제가 한 얘기들은 오직 제가 겪어본 경험에 기반으로 해서 틀린 부분이 있을 수 있습니다.
2012년 10월 4일 오후 10:34, fupfin <fup...@gmail.com>님 의 말:
그룹에서 탈퇴하려면 scala-korea...@googlegroups.com로 이메일을 보내주세요.
더 많은 옵션을 보려면 https://groups.google.com/groups/opt_out을 (를) 방문하세요.
--
========================================
블로그 : http://spyrogira256.blogspot.com윤재진 spyrog...@gmail.com
Google Talk. spyrogira256@gmail.com
NateOn. anjff...@lycos.co.kr
Mobile. 010-9747-8761
========================================
--
Google 그룹스 '라 스칼라 코딩단' 그룹에 가입했으므로 본 메일이 전송되었습니다.
이 그룹에 게시하려면 scala...@googlegroups.com(으)로 이메일을 보내세요.
그룹에서 탈퇴하려면 scala-korea...@googlegroups.com로 이메일을 보내주세요.
윤재진
죄송합니다 ^^;; 내용을 읽다가 마지막부분이 비슷한 부분이 있던거 같아서 남긴다고 남기고 보니 엉뚱한 말만 한거 같네요
핸드폰에서 보냄
윤재진
핸드폰에서 보냄
2012. 10. 4. 오후 10:34에 "fupfin" <fup...@gmail.com>님이 작성:
>
> 잘 정리해 주셔서 고맙습니다. ^^
>
> 한가지만 더, 제가 정말 토론하고 싶은 건데요.
>
> 제가 함수형 언어를 잘 모르는 편이라 맞는 말인지 모르겠지만, 하스켈이야 원래 반복문이 없으니 [물론, 따로 High Order Function(이걸 우리 말로 뭐라 고 하나요?)을 사용해서 반복문을 구현하기는 했지만] 꼬리 재귀로 선형적인 반복 구문을 표현한다고 하더라도, 스칼라는 (while, for 같은) 절차적 언어 의 반복 구문이 이미 있으니 굳이 선형적 반복을 꼬리재귀로 표현할 필요 없 이 반복문으로 코드를 표현해도 되지 않을까 싶습니다. (이 토론의 제목을 다 시 읽어 주시면... ^^)
>
다시 읽어보고 저만의 생각을 남기자면
Scala라는 언어적 특성때문에 꼬리 재귀와 while문을 비교하게 되는게 아닌지 싶습니다.
언어자체가 두가지를 전부 가능하게 해줘서 그런게 아닌지
선현적인 표현에서 while로 표현을 하게 되게 되는 부분은
전체적이 프로그래밍 방식을 함수형으로 작성을 하는 경우엔 약간은 그게 더 보는 사람에게는 불편하게 보이게 될꺼 같습니다.
함수형 프로그래밍에서 좋은점은 로직을 제외한 부분을 전부 추상화가 가능하게 하는게 좋은데 중간에 while이 들어가면
보기엔 좋을지 몰라도 어느부분에서 추상화 할때 추상화가 조금은 힘들게 되는게 아닌가 조심스럽게 생각해 봅니다.
실력이 미천해서 이while과 꼬리재귀의 비교 코드까지는 당장 표현이 안되네요
Hyunsok Oh
다 일리가 있는 말씀들이라 생각됩니다. 문제 도메인에 따라 달라지겠죠. 유클리드 호재법 같은 경우에는 루프로 구현시 오히려 이해하기 어려워 보입니다.
실용적으로 가독성을 높이는 방향으로 접근하는게 맞을것 같습니다.
다만 루프의 경우 함수언어계열에는 맵 필터 리듀스라는 걸출한 도구가 있고 보통 이를 활용하는 경우가 많죠. 보통 루프를 도는건 컬렉션 안의 객체를 방문하며 무언가 처리를 하는게 많은니까요...
핸폰이라 주저리 쓰기가 힘드네여