[질문] 함수 호출의 부하

힘내라의 이미지

C언어 공부한지 얼마 안된 학생입니다.

다름 아니라..

만약, A라는 함수안에서 B라는 함수를 로드하고

B에서 작업중 다시 A를 로드...

즉, 함수가 종료되지 않고. 계속 다른함수를 로딩하면서

프로그램이 실행되면은 쓰레드값 같은게 증가하는 건가요?

증가한다면 그 증가량은 클까요 아님 작을까요?

만약 증가하지 않는다면, 왜 증가하지 않는걸까요?

그리고, 프로그래머는 위와같은 상황을 피하기 위해

어떠한 방법으로 프로그램하는거죠?

이런 궁금증이 생긴게... 아무리 C++, JAVA의 클레스,상속이니 어쩌니 해도...

실제 컴퓨터는 튜링의 기계로 움직인다고 알고 있습니다. 하지만 프로그램을
하다보면

의도하든 의도하지 않든 위와 같은 상황은 충분히 일어날 수 있을꺼 같아서
생각이 난겁니다.

기만주니의 이미지

자료구조책에 보시면... O(log n) O(1)
Bio-O 표기법으로 복잡도를 설명해주는 게 있습니다.

그리고 연속된 함수 호출은 쓰레드생성과 무관 할겁니다...
쓰레드는 따로 생성을 해주는 API가 있거든요...

증가라함은... 아마 깊이의 증가를 말씀하시는게 아닌가 싶습니다.
깊이의 증가를 피해야하지만, 재귀적 함수 호출같이 가끔 피할수 없는 복잡도를 지니는 알고리듬들이 있습니다.

Bio-O 표기법을 보시면 대충 어떤 복잡도가... 어떤 성능을 내시는지 짐작할 수 있으리라 봅니다.

^^ 즐거움... 나를 이끄는 그 무엇..

익명 사용자의 이미지

함수를 호출할때마다 스택이 할당됩니다.

ㅡ,.ㅡ 저도 자세히는 모르구요..어셈블리 책 보면 그렇다고 하더라구요.

익명 사용자의 이미지

그리고 어쩔수 없이 재귀호출을 해야 할때가 있습니다.

가령 디렉터리를 몽땅 뒤져가면서 처리해야할 작업이 있다거나 할때 말이죠.

amister의 이미지

1. 함수가 호출될 때마다, 함수의 arguments와 local variables, 그리고 return value 등을 위한 stack이 할당됩니다. function stack이란 것이 있어서 프로그램이 실행후에 함수가 한 번 불릴 때마다 필요한 만큼 증가했다가 함수가 종료하면 줄어듭니다. 당연히 함수가 다른 함수를 계속 부른다면 그만큼 스택이 계속 증가합니다.

2. 만약 함수 A가 B를, 그리고 다시 B가 A를 부르는 상황이 발생하면 무한하게 함수 호출이 계속되면서 스택이 계속 증가하게 됩니다.

3. 제가 아는 한, 유닉스 시스템에서는 프로세스의 주소공간(address space)에 스택 영역이 따로 정해져있습니다. ulimit 등으로 확인 가능하며 일반적으로 8메가 정도로 정해져있습니다. 만약 함수 호출이 계속되면서 스택 사이즈가 증가하다가 영역을 벗어나게 되면 stack overflow가 발생합니다. 보통은 이러한 상황에서 segmentation fault를 보게 되겠죠. :(

4. 스택이 한정되어있기 때문에 함수 호출을 원하는대로 할 수 없는 상황이 발생하게 됩니다. 따라서 함수 호출할 때 그 함수에 대한 스택 증가량을 줄이는 것이 관건이며, 주로 불필요한 arguments를 줄이고 local variables의 수를 줄임으로써 해결합니다. 특히 array같은 큰 사이즈의 변수 등은 스택에 할당되지 않도록 heap 에 할당하고 - malloc()등을 사용하여 - 포인터 변수만 스택에 넣어놓음으로써 스택 사이즈를 크게 줄일 수 있습니다.

5. 어느 언어든 현재의 컴퓨터 시스템 위에서 동작하기 위하여 튜링 머신의 형태에 맞는 코드를 생성합니다. 생성되는 코드는 언어의 특성과 컴파일러에 따라 좌우되기 때문에, 언어와 사용하는 컴파일러에 대한 이해가 충분해야 합니다.

힘내라의 이미지

역시 함수 로딩시 메모리에 부하가 걸리는게 맞군요.

답변해주신 모든 분들 감사합니다 ^_^

...살아서 굴욕을 받느니!
분투 중에 쓰러지리라!

lacovnk의 이미지

Anonymous wrote:
그리고 어쩔수 없이 재귀호출을 해야 할때가 있습니다.

가령 디렉터리를 몽땅 뒤져가면서 처리해야할 작업이 있다거나 할때 말이죠.

재귀호출을 안 쓰고 가능할 것 같은데 (순전히 짐작 ㅎ).. 가능한가요?

큐를 이용해서 BFS를 하면 될 것 같은데.. upper directory는 ".."로 접근할 수 있겠지요?

으음.. 근데 큐를 동적으로 관리해야 하는 압박이 있는건가.. -_-;

htna의 이미지

lacovnk wrote:
Anonymous wrote:
그리고 어쩔수 없이 재귀호출을 해야 할때가 있습니다.

가령 디렉터리를 몽땅 뒤져가면서 처리해야할 작업이 있다거나 할때 말이죠.

재귀호출을 안 쓰고 가능할 것 같은데 (순전히 짐작 ㅎ).. 가능한가요?

큐를 이용해서 BFS를 하면 될 것 같은데.. upper directory는 ".."로 접근할 수 있겠지요?

으음.. 근데 큐를 동적으로 관리해야 하는 압박이 있는건가.. -_-;


물론 queue를 사용하는 경우가 있습니다만, 그 경우는 매우 한정적입니다.
특정한 상황이란 얘기죠.. 하지만. 일반적으로 저런경우 queue보다 stack을 이용합니다.
즉 함수호출을 가상으로 시뮬레이션 합니다.

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

체스맨의 이미지

모든 재귀 호출 알고리즘은 비재귀 호출로 전환할 수 있습니다.

재귀 호출은 만들때는 간단해서 좋은데, 쓰다 보면 스택 초과가
일어나는 상황이 언젠가는 오게 되는 것 같아서, 저 같은 경우는
왠만하면 비재귀로 전환합니다.

Orion Project : http://orionids.org

htna의 이미지

체스맨 wrote:
모든 재귀 호출 알고리즘은 비재귀 호출로 전환할 수 있습니다.

재귀 호출은 만들때는 간단해서 좋은데, 쓰다 보면 스택 초과가
일어나는 상황이 언젠가는 오게 되는 것 같아서, 저 같은 경우는
왠만하면 비재귀로 전환합니다.


모든 재귀함수 호출을 비재귀로 바꿀 수 있나요?
물론 함수 내부에 스택을 만들고, 이를 이용해서 재귀함수 호출을 시뮬레이션 할 수는 있지만... 이 또한 한정적인 형태의 모양일 때만 가능하다고 생각합니다만...
모두 만들수 있다는것은 처음 들었습니다.
다만 재귀함수 호출시 생기는 부하를.
tail recursion 으로 바꿈으로서 재귀함수 호출을 없앨수는 있는것으로 알고 있습니다만. 이는 경우에 따라 가능한 것이죠...

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

체스맨의 이미지

htna wrote:

모든 재귀함수 호출을 비재귀로 바꿀 수 있나요?

재귀호출이 결국 프로그램 스택을 이용하기 때문에,
비재귀로 구현할 수 없는 리커젼 알고리즘은 있을 수가 없습니다.

구현이 어려운 것은 있어도 불가능한 것은 없는 것으로 알고 있습니다.

Orion Project : http://orionids.org

htna의 이미지

체스맨 wrote:
htna wrote:

모든 재귀함수 호출을 비재귀로 바꿀 수 있나요?

재귀호출이 결국 프로그램 스택을 이용하기 때문에,
비재귀로 구현할 수 없는 리커젼 알고리즘은 있을 수가 없습니다.

구현이 어려운 것은 있어도 불가능한 것은 없는 것으로 알고 있습니다.


스택을 내부적으로 구현하여 '재귀함수'를 시뮬레이션 하는것이...
물론 재귀는 아닙니다만.
그렇다고 '비 재귀' 라고 얘기하기도 애매하다고 생각하기에...
저렇게 얘기를 한 것입니다..
하지만...
tail recursion의 경우에는 완전한 비 재귀에 속하지요...

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

체스맨의 이미지

스택없이 비재귀로 전환하는 제약 조건이 있다면 비재귀로 구현할 수 없는 것이 많겠습니다만....

왜 스택으로 구현하는 것을 재귀함수를 시뮬레이션 한다고 생각하시는 지요? 알고리즘을 스택을 이용해서 구현했다고 생각하시면 될 것 같은데요.

자료 구조 관련 서적에서도 비재귀로 전환 부분에서 스택을 이용하는 예들이 나옵니다. 혹시 '스택을 이용하는 것이 재귀함수를 시뮬레이션 하는 것이다' 라던가, '스택을 이용하면 완전한 비재귀라 볼 수 없다'고 나온 참고 문헌이 있으면 알려주시기 바랍니다.

Orion Project : http://orionids.org

익명 사용자의 이미지

호출회수를 제한적으로 부르는거는 어떨까요...

arg로 호출 회수를 인자로 보내거나
로컬변수를 이용해서 call 때마다 증가를 시켜서
제한을 두는겁니다..

재귀를 사용하고 싶고 스택 오버플로를 방지하는
방법이요 ^^

htna의 이미지

체스맨 wrote:
스택없이 비재귀로 전환하는 제약 조건이 있다면 비재귀로 구현할 수 없는 것이 많겠습니다만....

왜 스택으로 구현하는 것을 재귀함수를 시뮬레이션 한다고 생각하시는 지요? 알고리즘을 스택을 이용해서 구현했다고 생각하시면 될 것 같은데요.

자료 구조 관련 서적에서도 비재귀로 전환 부분에서 스택을 이용하는 예들이 나옵니다. 혹시 '스택을 이용하는 것이 재귀함수를 시뮬레이션 하는 것이다' 라던가, '스택을 이용하면 완전한 비재귀라 볼 수 없다'고 나온 참고 문헌이 있으면 알려주시기 바랍니다.


관념적인 차이겠군요..
특별히 그러하게 언급한 서적이나 문헌이 있는것은 아닙니다.
(머 있을수도 있겠지만... 굳이 이 문제를 들고나올 필요는 없죠.)
저의 경우에는 일단 간단하게 처리할 수 있으면, 그렇게 나갑니다.
나중에 문제가 되거나, 처음부터 문제가 될 소지가 있는 부분에 대해서만 내부적으로 스택을 구성해서 처리하지요...
(수행시간의 문제와 과도한 메모리낭비 문제가 큰 이유겠지만요..)
그래서인지, 그러한 목적을 가진 내부적인 스택을 이용한 구성은, 재귀함수로 처리해야 할 것들을 스택을 이용하여 편법으로 처리한다, 고 생각하는 편입니다.
그렇기에 재귀함수를 시뮬레이션 한다고 표현하는 것이지요.
하지만, tail recursion은 재귀함수를 완전히 없앨 수 있는 방법이기에 '비 재귀'다 라고 구분짓는 것이구요...

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

전웅의 이미지

흠... 우연히 글을 읽다가 비슷한 이야기가 떠올라 링크를 걸어봅니다.

http://www.woong.org/board/?doc=bbs/gnuboard.php&bo_table=cfund&wr_id=93

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

creativeidler의 이미지

리얼타임이 아니라면 함수 호출의 오버헤드는 철저히 무시하는 게 좋습니다. 그 정도 오버헤드 때문에 코드의 지저분함을 감수할 필요는 없습니다.

재귀호출을 Dynamic Programming이라든지 앞서의 스택을 이용한 방법 등으로 풀 수 있긴 합니다만 재귀호출의 또다른 장점이 트리 구조 같은 자료구조를 명료한 코드로 다룰 수 있다는 것인데 그 장점을 포기할 정도로 오버헤드가 크진 않습니다. 당신들의 PC는 이미 엄청나게 빠릅니다-_-

XP에서는 Lazy Optimization & Early Profiling을 권장합니다. 성능 문제는 프로파일링을 통해 극복해 나가시고 속설에 의지하지 마십시오.

전웅의 이미지

creativeidler wrote:
리얼타임이 아니라면 함수 호출의 오버헤드는 철저히 무시하는 게 좋습니다. 그 정도 오버헤드 때문에 코드의 지저분함을 감수할 필요는 없습니다.

재귀호출을 Dynamic Programming이라든지 앞서의 스택을 이용한 방법 등으로 풀 수 있긴 합니다만 재귀호출의 또다른 장점이 트리 구조 같은 자료구조를 명료한 코드로 다룰 수 있다는 것인데 그 장점을 포기할 정도로 오버헤드가 크진 않습니다. 당신들의 PC는 이미 엄청나게 빠릅니다-_-

XP에서는 Lazy Optimization & Early Profiling을 권장합니다. 성능 문제는 프로파일링을 통해 극복해 나가시고 속설에 의지하지 마십시오.

단순히 "성능"만을 위해서 재귀호출을 피하는 것은 아닙니다.

제가 앞서 링크한 글에도 나와 있지만, 재귀호출을 스택을 사용해 비재귀
형태로 바꿀 경우 스택에 대한 제어권이 철저히 프로그래머에게 넘어온다는
장점이 있습니다.

따라서 글에서도 이미 밝혔지만, 충분한 profiling 을 통해 성능에 대한
기여도가 적고 재귀호출의 깊이가 실질적인 상황에서도 충분히 깊지 않다는
것을 확신할 수 있을 때에만 제품 코드에서 재귀호출을 그대로 두는 것이
이익이 된다는 것이 제 개인적인 관점입니다.

단, 성능에 대한 기여도가 높지 않더라도 재귀의 깊이가 임의로 깊어질 수
있다면 제품 코드에서는 반드시 별도 구현된 스택을 사용한 비재귀 호출을
사용하는 것이 바람직하다고 봅니다.

물론, 위에서 다른 분이 잠시 언급하신 것처럼 재귀의 깊이를 인자 전달을
통해 제한하는 것도 한가지 방법이 될 수 있겠습니다만, 이는 현재
프로세스에 할당된 스택에 대한 조사 없이는 dynamic 하게 실행 환경에
적응하지 못한다는 단점이 있기에 근본적인 해결책은 될 수 없습니다.

실제 개발 과정에서 정해진 원칙에 따라 달라질 수 있는 부분이겠지만,
제가 프로젝트를 관리하는 입장이라면 말씀하신 profiling 을 통한 증명을
보여주지 못하는 이상, 기본적으로 비재귀 형태로의 전환을 요구할
것입니다. 그 기저에는 프로그래머의 편의보다 제품의 안정성을
중요시한다는 생각이 있다고 보시면 됩니다.

p.s. 시험만 다가오면 갑자기 평소엔 안 하던 일이 막 하고 싶어
지는군요. --;

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

amister의 이미지

전웅님 말씀에 동의합니다.

성능이야, 최신 컴파일러들의 스택 최적화가 잘 이루어지는 편이기 때문에 비재귀호
출로 바꾼다고 해서 일반적으로 성능향상이 많이 되는것은 아니죠. 하지만 컨텍스트
를 직접 컨트롤 할 수 있다는 점에서 메리트가 생길 수 있는 상황이 많이 발생합니
다. 디버깅이 용이한 점도 있겠군요. (저만의 생각인가요?)

어쨌거나, 개인적으로는 일단 재귀호출이든 아니든 자신이 편하고 쉽게 생각할 수
있는 방향으로 먼저 개발하고 나서 최적화 과정에서 다른 방식으로 변경하면 된다
고 생각합니다. 그를 위해서는 호출방식의 변경으로 인한 side effect를 최소화하도
록 다른 코드를 작성해야겠죠. 일반론적인 얘기라 여기서 끝내겠습니다.

creativeidler의 이미지

프로그래머의 편의보다 제품의 안정성? 뭔가 비교 대상이 아닌 것을 비교했다는 느낌이 드는군요. 프로그래머가 빠르게 코드를 작성할 수 있고 또 알아보기 쉬운 코드를 작성할 수 있다면 그만큼 버그 발생 확률도 줄어들고 안정성은 높아집니다. 재귀 호출로 쉽게 할 수 있는 걸 억지로 비재귀 호출로 바꾼다면 버그가 발생할 수 있는 포인트가 늘어나는 것 뿐이죠.

스택에 대한 제어권이 프로그래머에게 이득이 된다는 것도 납득하기 힘들군요. 어차피 중요한 건 functionality의 구현이고 스택 직접 제어라는 장점이 functionality의 구현에 별다른 영향을 주지 않는 이상 성능 이외에 이점이 있다고는 하기 힘들 텐데요.

profiling으로 증명을 보여주지 못하는 이상 비재귀 형태로의 전환을 요구한다고 하셨는데, 실무에서는 오히려 그 반대로 가야 합니다. 비재귀 호출로의 전환은 dynamic programming으로 전환할 수 있는 경우가 아닌, 스택 컨트롤을 통한 전환이라면 재귀 호출에 비해 더 많은 노력이 듭니다. 성능상의 확실한 이득이 있지 않은 이상 추가적인 인력을 투입하는 것은 시간 낭비입니다. 성능 향상조차도 단순히 그 지점의 성능 향상을 증명하는 것만으로도 부족하고 그 지점이 전체 시스템에서 병목지점이라는 것까지를 증명해내야 비로소 그 지점을 최적화할 명분을 갖게 되는 것입니다.

요즘은 임베디드 시스템에서도 요즘은 hard real time이 아닌 이상 병목 지점이 아닌 부분의 최적화는 잘 수행하지 않습니다. time to market이 점점 중요해지고 있기 때문에 가장 빨리, 그리고 가장 이해하기 쉽게 구현하는 것이 더 중요합니다.

가장 좋은 최적화는 최적화를 위해 아무 것도 하지 않는 것이다. 라는 말도 있죠. 성능은 제일 마지막에 고려하십시오. 그것이 당신의 코드를 "사람이 알아볼 수 있는 코드"로 만드는 데 기여할 것입니다.

전웅의 이미지

creativeidler wrote:
프로그래머의 편의보다 제품의 안정성? 뭔가 비교 대상이 아닌 것을 비교했다는 느낌이 드는군요. 프로그래머가 빠르게 코드를 작성할 수 있고 또 알아보기 쉬운 코드를 작성할 수 있다면 그만큼 버그 발생 확률도 줄어들고 안정성은 높아집니다. 재귀 호출로 쉽게 할 수 있는 걸 억지로 비재귀 호출로 바꾼다면 버그가 발생할 수 있는 포인트가 늘어나는 것 뿐이죠.

재귀-비재귀의 변환은 지극히 기계적인 작업에 의해 가능합니다. 일부
알고리즘 서적의 경우 알고리즘에 대한 의미적인 이해 없이도 주어진
단계를 거쳐 재귀적 구현을 비재귀로 변환하는 방법을 다루기도 합니다.
여기에 알고리즘에 대한 이해가 더해질 경우, 실제 스택에 유지하지 않아도
되는 정보, 혹은 불필요한 잔작업에 대한 배제가 가능할 뿐입니다. 더구나
실무에서 사용되는 알고리즘의 복잡도가 이론적으로 제안되고 연구되는
알고리즘에 비해 까다롭지 않다는 점을 감안할 때 실제 재귀-비재귀의
변환이 버그 발생 가능성을 높인다고 보기는 어렵습니다. 또한, 조금이라도
그와 같은 가능성이 있다면 이는 악의적인 사용자에 의해 생길 수 있는
프로그램 전반에 영향을 주는 위험성을 위해 충분히 희생할 가치가 있다고
봅니다.

이와 같은 논점에서 프로그래머의 편의와 제품의 안정성이라는 대조가
이루어진 것입니다.

분명, 재귀적 구현의 장점은 재귀적으로 쉽게 기술될 수 있는 알고리즘을
논리적 결함 없이 빠르게 구현으로 옮길 수 있다는데 있습니다. 그와 같은
재귀적 구현의 장점 까지도 애써 무시하며 비재귀를 강조하는 것은
아닙니다. 이미 실질적인 모든 가능성을 고려했을 때 안정성이 확보된다면
오히려 재귀적 호출이 프로그램의 가독성이나 유지 보수에 탁월함을
말씀드린바 있습니다 (링크된 글을 보시기 바랍니다). 하지만, 그렇지 않은
경우, 말씀하신대로 성능 문제는 감안하지 않더라도, 프로그램이 임의의
입력에 대해 비정상 종료할 수 있는지 혹은 어차피 맡은 바 기능을
수행하지 못하더라도 스택에 대한 제어를 통해 프로그램의 정상적인 수행을
유지할 수 있는지 여부는 매우 큰 차이입니다.

creativeidler wrote:
스택에 대한 제어권이 프로그래머에게 이득이 된다는 것도 납득하기 힘들군요. 어차피 중요한 건 functionality의 구현이고 스택 직접 제어라는 장점이 functionality의 구현에 별다른 영향을 주지 않는 이상 성능 이외에 이점이 있다고는 하기 힘들 텐데요.

어차피 스택이 고갈된 상태라면 재귀적 구현도 functionality 를 유지할
수 없습니다. 차이는 앞서 말씀드린 것처럼, 좀 더 우아하게 프로그램의
비정상적인 행동을 막을 수 있다는데 있습니다. 최소한, "엄마! 여기에
10000000을 입력하니깐 옆집 컴퓨터가 멈췄어" 라는 이야기는 나오지는
말아야 한다는 것입니다.

creativeidler wrote:
profiling으로 증명을 보여주지 못하는 이상 비재귀 형태로의 전환을 요구한다고 하셨는데, 실무에서는 오히려 그 반대로 가야 합니다. 비재귀 호출로의 전환은 dynamic programming으로 전환할 수 있는 경우가 아닌, 스택 컨트롤을 통한 전환이라면 재귀 호출에 비해 더 많은 노력이 듭니다. 성능상의 확실한 이득이 있지 않은 이상 추가적인 인력을 투입하는 것은 시간 낭비입니다. 성능 향상조차도 단순히 그 지점의 성능 향상을 증명하는 것만으로도 부족하고 그 지점이 전체 시스템에서 병목지점이라는 것까지를 증명해내야 비로소 그 지점을 최적화할 명분을 갖게 되는 것입니다.

요즘은 임베디드 시스템에서도 요즘은 hard real time이 아닌 이상 병목 지점이 아닌 부분의 최적화는 잘 수행하지 않습니다. time to market이 점점 중요해지고 있기 때문에 가장 빨리, 그리고 가장 이해하기 쉽게 구현하는 것이 더 중요합니다.

이야기를 자꾸 성능 문제로 가져가셔서 논점을 흐리시지 않았으면 합니다.
이미 성능이 매우 민감한 지극히 특수한 분야를 제외하고는 단순히 성능
때문에 재귀를 비재귀로 바꿀 필요는 없다는 사실에는 충분한 동의가
있었다고 봅니다.

예를 들어, 충분한 검증 없이 재귀적 알고리즘으로 트리 탐색을 하는 보안
관련 프로그램이 악의적으로 전송돼온 테이블을 받아 탐색을 시도하다가
stack overflow 로 프로세스 전체가 종료되는 일은 막아야 한다는 것이 제
이야기의 논점입니다. 이는 결코 성능에 대한 이야기가 아닙니다. 앞서
언급하신 "게으른 최적화" 가 프로그램의 잠재적 위험성까지 무시하며
게으르게 하자는 뜻은 아니라고 봅니다.

creativeidler wrote:
가장 좋은 최적화는 최적화를 위해 아무 것도 하지 않는 것이다. 라는 말도 있죠. 성능은 제일 마지막에 고려하십시오. 그것이 당신의 코드를 "사람이 알아볼 수 있는 코드"로 만드는 데 기여할 것입니다.

다시 한번 말씀드리지만, 제가 드리는 말씀의 논점은 성능을 위한 최적화가
아닙니다.

안정성은 제일 처음에 고려하십시오. 그것이 당신의 코드를 사용하는
사용자가 해킹을 당하는 불미스러운 일이나 패치를 받아 설치해야 하는
번거로운 일을 막는 데 기여할 것입니다.

분명, 님께서도 단지 성능만을 위해 무조건 재귀를 비재귀로 바꾸는 것은
옳지 않지만, 프로그램이 가질 수 있는 잠재적 위험성까지 무시하면서
재귀를 유지하자고 주장하시는 것은 아니라고 봅니다.

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

happyjun의 이미지

그런데 재귀호출로 구현한 곳에 악의적으로 stack overflow를 일으킬 수 있다면 비재귀로 구현해도 무한 반복에 빠지지 않나요?

이런 문제라면 입력값 검사 문제이지 재귀 대 비재귀의 문제는 아니라고 봅니다.

----------------------------------------
http://moim.at
http://mkhq.co.kr

전웅의 이미지

happyjun wrote:
그런데 재귀호출로 구현한 곳에 악의적으로 stack overflow를 일으킬 수 있다면 비재귀로 구현해도 무한 반복에 빠지지 않나요?

이런 문제라면 입력값 검사 문제이지 재귀 대 비재귀의 문제는 아니라고 봅니다.

그렇지 않습니다.

비재귀로 구현할 경우 스택 할당과 해제를 implementation 이 아닌
프로그램이 하게 됩니다. 즉, malloc 등의 일반적인 메모리 할당 절차를
통해 할당된 메모리를 스택으로 사용하는 것이기 때문에 재귀의 깊이가
깊어짐으로써 발생할 수 있는 stack overflow 를 사전에 감지할 수 있다는
장점이 있습니다.

입력값을 검사하는 방법은 앞서 말씀드린 재귀의 깊이를 함수 인자 등으로
제한하는 방법과 근본적으로 다르지 않습니다. 즉, 실행 환경의 변화에
따라 동적으로 적응하지 못하는 불완전한 해결책입니다.

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

creativeidler의 이미지

1. stack overflow를 예방할 방법은 얼마든지 있습니다. 현대적인 예외 처리가 있는 언어들이라면 이건 고민 거리도 아니죠. 안정성 안정성 하시는데 안정성이 중요한 DB에서도 재귀 호출은 많이 사용됩니다.

2. 많은 경우 stack overflow 문제는 입력의 문제, 즉 환경적인 방법으로도 충분히 제어할 수 있습니다.

3. stack overflow를 직접 제어한다는 것이 장점일지 단점일지는 다시 생각해보시기 바랍니다. 컴파일러, 혹은 OS가 해야할 일을 프로그래머가 하는 것이 좋을까요?

creativeidler의 이미지

Quote:
이야기를 자꾸 성능 문제로 가져가셔서 논점을 흐리시지 않았으면 합니다.

이런 말씀을 하셨는데...

Quote:
profiling 을 통한 증명을
보여주지 못하는 이상, 기본적으로 비재귀 형태로의 전환을 요구할
것입니다.

이렇게 말씀하셨던 것을 잊으신 것 아닌가요? 이 말에 대한 반론으로 성능 이슈를 거론하는 것은 당연해보이는데요-_-

물론 사실 저 말 자체가 님의 주된 논지와 거리가 있죠-_- 님은 성능 문제가 있든 없든 비재귀 형태로의 전환이 좋다고 말씀하시면서 profiling을 통해 증명할 경우는 재귀 형태를 유지해도 좋다고 말씀하시니...

전웅의 이미지

creativeidler wrote:
1. stack overflow를 예방할 방법은 얼마든지 있습니다. 현대적인 예외 처리가 있는 언어들이라면 이건 고민 거리도 아니죠. 안정성 안정성 하시는데 안정성이 중요한 DB에서도 재귀 호출은 많이 사용됩니다.

OP 의 질문을 인용합니다.

힘내라 wrote:
C언어 공부한지 얼마 안된 학생입니다.

이 문맥에서 stack overflow 를 예방할 수 있는 "이식성" 있는 방법을 알려
주시기 바랍니다. 설마 매번 재귀호출이 일어날 때마다 inline asm 을 써서
stack pointer 의 값을 검사해야 하는 것은 아니겠지요?

creativeidler wrote:
2. 많은 경우 stack overflow 문제는 입력의 문제, 즉 환경적인 방법으로도 충분히 제어할 수 있습니다.

자신의 프로그램이 가능한 다양한 환경에서 컴파일될 수 있을 때 (혹은
그렇게 되고자 노력할 때), 구체적으로 어떻게 입력을 제한해야 stack
overflow 를 예방할 수 있을까요? 역시나 경험적으로 "내가 사용해 본 가장
후진 컴퓨터에서 10번까지는 호출이 가능했으니 재귀의 깊이가 10번 미만이
되도록 제한하자" 라는 식의 접근은 아니라고 봅니다.

creativeidler wrote:
3. stack overflow를 직접 제어한다는 것이 장점일지 단점일지는 다시 생각해보시기 바랍니다. 컴파일러, 혹은 OS가 해야할 일을 프로그래머가 하는 것이 좋을까요?

다시 생각해 보았지만, 아무리 생각해도 "C 언어"를 사용해 프로그램을
작성할 때는 큰 장점 중 하나입니다.

C 언어의 가장 큰 장점 중 하나가 다른 언어에 비해 메모리 관리에 대한
제어권이 프로그래머에게 많다는 것입니다. 권리에는 책임이 따르지만, 그
책임을 다 했을 때 얻을 수 있는 것은 많습니다.

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

전웅의 이미지

creativeidler wrote:
Quote:
이야기를 자꾸 성능 문제로 가져가셔서 논점을 흐리시지 않았으면 합니다.

이런 말씀을 하셨는데...

Quote:
profiling 을 통한 증명을
보여주지 못하는 이상, 기본적으로 비재귀 형태로의 전환을 요구할
것입니다.

이렇게 말씀하셨던 것을 잊으신 것 아닌가요? 이 말에 대한 반론으로 성능 이슈를 거론하는 것은 당연해보이는데요-_-

물론 사실 저 말 자체가 님의 주된 논지와 거리가 있죠-_- 님은 성능 문제가 있든 없든 비재귀 형태로의 전환이 좋다고 말씀하시면서 profiling을 통해 증명할 경우는 재귀 형태를 유지해도 좋다고 말씀하시니...

보고자 하시는 부분만 잘라 보시면 그와 같은 오해가 가능합니다.

profiling 을 언급한 원글은 이 부분입니다.

전웅 wrote:
충분한 profiling 을 통해 성능에 대한
기여도가 적고 재귀호출의 깊이가 실질적인 상황에서도 충분히 깊지 않다는
것을 확신할 수 있을 때에만 제품 코드에서 재귀호출을 그대로 두는 것이
이익이 된다는 것이 제 개인적인 관점입니다.

A = "profiling 을 통해 성능에 대한 기여도가 중요하지 않음을 확인했음"
B = "실질적인 상황에서도 재귀의 깊이가 깊지 않다는 것을 확인했음"

이라고 할 때, 제가 개인적으로 재귀적 구현을 비재귀로 바꾸지 않는
상황은 A 와 B 가 모두 참인 경우입니다.

즉, 인용하신 부분은 A, B 두 경우 중 하나라도 만족되지 못하면 비재귀로
바꾸어야 한다는 이야기를 하고 있는 부분입니다.

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

creativeidler의 이미지

방법. 간단하죠. stack의 max를 앞에서 미리 재놓고 함수 호출 회수를 재서 비교하면 됩니다. 어차피 비재귀로 하더라도 비슷한 방법이죠. 어차피 비재귀로 변환해서까지 막고 싶다면 inline asm 처음에 몇 줄 들어가는 정도를 부담이라고 할 순 없겠죠.

환경적인 방법? stack overflow가 어떤 경우에 많이 일어난다고 생각하십니까? 재귀 호출이 사용되는 가장 많은 케이스가 트리 구조의 탐색 아니면 큰 데이터의 divide & conquer인데 트리의 depth가 stack overflow를 유발할 정도로 깊은 경우는 극히 드물고 큰 데이터의 경우 PC에서 10억건을 quick sort해도 stack overflow 안 일어납니다. PC에서 stack overflow가 일어난다는 얘기는 거의 십중팔구 무한루프이고 이건 대부분 이미 버그거나 애플리케이션의 경계 조건을 제대로 검사하지 않는 것입니다. 고로 stack overflow를 막는 쉬운 방법은 애플리케이션의 영역을 비상식적으로 벗어난 입력을 통제하는 것입니다.

그리고 경험적인 통계로 약간의 오차 범위를 포함한 영역을 통제하는 것도 공학적으로는 충분히 좋은 방법입니다. 아파치에서 Max process나 thread 값 등이 어떻게 결정된 거라고 생각하십니까? 공학에서 필요한 것은 비용 대비 효과를 극대화하는 것이지 stack을 딱 한계지점까지 쓰는 그런 게 아닙니다.

creativeidler의 이미지

Quote:
보고자 하시는 부분만 잘라 보시면 그와 같은 오해가 가능합니다.

말은 바로 하고 넘어가죠-_- 제가 보고 싶은 부분만 잘라 인용한 게 아니라 님이 자신의 앞서의 주장을 왜곡해서 요약했다는 게 맞는 말 아닌가요. B는 분명 profiling을 통한 증명이란 표현에 포함이 안되죠. 님의 주장은 다음과 비슷합니다.

A 조건과 B 조건이 있으면 C가 됩니다.
...
...

그러므로, A 조건이 있으면 C가 됩니다.

이렇게 써 놓으셨으면서 보고 싶은 부분만 본 거라고 하면 곤란하죠-_- 머, 이 정도 실수는 충분히 할 수 있는 일이니 그냥 실수라 인정하시면 넘어갈 수 있는 일일 텐데요.

전웅의 이미지

creativeidler wrote:
방법. 간단하죠. stack의 max를 앞에서 미리 재놓고 함수 호출 회수를 재서 비교하면 됩니다.

그 max 를 정적으로 미리 결정하기가 쉽지 않다는 것입니다. 이 프로그램은
이 버전의 이 환경, 이 버전의 이 컴파일러, 이 버전의 이 링커로 번역되고
각종 시스템 변수가 이렇게 설정되어 있을 때에만 stack overflow 없이
작동한다고 보장하는 것은 프로그램의 유연성을 불필요하게 제한하는
길입니다. 또한, 그와 같은 치명적인 값을 (무지할 수도 있는) 사용자에게
선택하라고 부담을 넘기는 것 역시 바람직하지 않다고 봅니다.

creativeidler wrote:
어차피 비재귀로 하더라도 비슷한 방법이죠.

앞서 말씀드렸듯이 재귀적 구현을 비재귀로 변환할 때는 그와 같은 정적인
상한선을 정해줄 필요가 없습니다. 간단한 재귀적 알고리즘을 구현한 후에
이를 malloc 등의 동적 할당을 사용하는 스택을 이용하는 비재귀로 변환해
보시기 바랍니다.

creativeidler wrote:
어차피 비재귀로 변환해서까지 막고 싶다면 inline asm 처음에 몇 줄 들어가는 정도를 부담이라고 할 순 없겠죠.

차이는 이식성에 있습니다. 스택을 이용해 비재귀로 구현할 경우에는
프로그램의 이식성에 주는 영향이 전혀 없지만, 인라인 어셈블리어를
사용해 해당 프로세스에 할당된 실직적인 스택 크기를 구하고 현재 함수가
사용하는 스택의 깊이를 추적하는 일은 지극히 환경 의존적인 일입니다.
이 둘 사이에는 어마어마한 차이가 존재합니다.

creativeidler wrote:
환경적인 방법? stack overflow가 어떤 경우에 많이 일어난다고 생각하십니까? 재귀 호출이 사용되는 가장 많은 케이스가 트리 구조의 탐색 아니면 큰 데이터의 divide & conquer인데 트리의 depth가 stack overflow를 유발할 정도로 깊은 경우는 극히 드물고 큰 데이터의 경우 PC에서 10억건을 quick sort해도 stack overflow 안 일어납니다. PC에서 stack overflow가 일어난다는 얘기는 거의 십중팔구 무한루프이고 이건 대부분 이미 버그거나 애플리케이션의 경계 조건을 제대로 검사하지 않는 것입니다. 고로 stack overflow를 막는 쉬운 방법은 애플리케이션의 영역을 비상식적으로 벗어난 입력을 통제하는 것입니다.

stack overflow 는 의외로 쉽게 일어날 수 있습니다. 예를 들어, 재귀의
깊이가 결코 깊지 않더라도 한번 호출되는 함수에서 사용하는 스택의 양이
적지 않을 경우에는 낮은 깊이의 재귀 호출에서도 overflow 가 발생합니다.

또한, 일례로 AI 분야에서 개발된 탐색 알고리즘을 프로그램 개발에 적용할
때도 문제의 규모와 초기 상태에 따라 재귀의 깊이가 상상을 초월할 수
있습니다.

creativeidler wrote:
그리고 경험적인 통계로 약간의 오차 범위를 포함한 영역을 통제하는 것도 공학적으로는 충분히 좋은 방법입니다. 아파치에서 Max process나 thread 값 등이 어떻게 결정된 거라고 생각하십니까? 공학에서 필요한 것은 비용 대비 효과를 극대화하는 것이지 stack을 딱 한계지점까지 쓰는 그런 게 아닙니다.

사용자가 정적으로 설정해 줄 수 있는 변수가 프로그램의 성능에 영향을
미칠 순 있어도 프로그램의 작동/오작동 여부에 영향을 주지 않는다면
충분히 정적인 매개변수에 의존할 수 있습니다. 재귀 호출의 깊이에 따른
stack overflow 문제는 프로그램의 작동/오작동과 연관된 부분입니다.

또한, 말씀하신 것처럼 "경험적인 통계로 약간의 오차 범위를 포함한
영역을 통제하는 것" 은 결국 실제 충분히 가능한 환경에서 해당
프로그램의 재귀 호출 구현이 올바르게 동작함을 보이는 것과 같은
이야기에 해당합니다. 예를 들어, 재귀 호출을 사용하는 A 라는 프로그램이
제한된 범위의 출력을 갖는 B 라는 프로그램에 의해서만 호출이 되고, 그와
같은 범위의 입력값에 대해서 A 프로그램이 사용하는 재귀 호출 알고리즘이
stack overflow 를 일으키는 것이 현실적으로 불가능하다고 판단될
경우에는 충분히 재귀적 구현에 의존할 수 있습니다 (이는 앞서 말씀드린
가정 중 B 의 경우가 만족되는 경우에 해당합니다). "통계"에 의한 영역
통제와 제가 말씀드린 "10 정도로 제한하면 되겠지" 같은 가정을 통한
통제는 system 의 유무라는 큰 차이를 갖는 경우입니다.

곧 이 글타래를 잠그자는 의견이 나올까봐 걱정스럽습니다만, 저는 이미
님이 주장하시는 바가 충분히 동의을 얻었음에도 억지를 부리고 계신 것이
아닌가 조금스럽게 생각합니다.

애초부터 성능이라는 factor 에만 의존해 무조건 재귀를 비재귀로 바꾸는
것은 성급한 최적화일 뿐이라는 사실에는 동의가 이루어진 상태이며,
C 언어와 같이 예외 처리에 약하고, 메모리에 대한 제어권 상당 부분이
프로그래머에게 주어져 있으며, 또한 프로그램 오작동 시에 시스템에
치명적 영향을 줄 수 있는 문맥에서는 충분한 검증 없이는 재귀적 구현을
그대로 두는 것은 제품 코드에서는 피해야 하는 일이라는 게 제 주장의
요지입니다.

님께서 그와 같은 상황에서조차 무조건 재귀 호출에 의존해야 한다고
주장하고 계신다고는 믿지 않습니다.

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

전웅의 이미지

creativeidler wrote:
Quote:
보고자 하시는 부분만 잘라 보시면 그와 같은 오해가 가능합니다.

말은 바로 하고 넘어가죠-_- 제가 보고 싶은 부분만 잘라 인용한 게 아니라 님이 자신의 앞서의 주장을 왜곡해서 요약했다는 게 맞는 말 아닌가요. B는 분명 profiling을 통한 증명이란 표현에 포함이 안되죠. 님의 주장은 다음과 비슷합니다.

A 조건과 B 조건이 있으면 C가 됩니다.
...
...

그러므로, A 조건이 있으면 C가 됩니다.

이렇게 써 놓으셨으면서 보고 싶은 부분만 본 거라고 하면 곤란하죠-_- 머, 이 정도 실수는 충분히 할 수 있는 일이니 그냥 실수라 인정하시면 넘어갈 수 있는 일일 텐데요.

해당 부분으로 오해를 일으켰다면 사과 말씀드립니다. 님이 생각하고
계시는 문맥에서의 profiling 이 제가 생각하고 있던 profiling 과 다름을
보다 분명히 밝히지 못했습니다. (profiling 이 배타적으로 성능에 대한
factor 만을 보고해 주는 것은 아닙니다. 예를 들어, profiler 중 하나인
gprof 역시 특정 함수에 대해 재귀가 아닌 방식으로 호출된 횟수와 재귀로
호출된 횟수를 구분해 보여줄 수 있습니다. 다시 말해, 함수의 재귀 호출
깊이를 실험적으로 파악하고자 할 때도 profiler 가 중요한 역할을 할 수
있습니다.)

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

creativeidler의 이미지

Quote:
그 max 를 정적으로 미리 결정하기가 쉽지 않다는 것입니다.

Quote:
차이는 이식성에 있습니다. 스택을 이용해 비재귀로 구현할 경우에는
프로그램의 이식성에 주는 영향이 전혀 없지만, 인라인 어셈블리어를
사용해 해당 프로세스에 할당된 실직적인 스택 크기를 구하고 현재 함수가
사용하는 스택의 깊이를 추적하는 일은 지극히 환경 의존적인 일입니다.

정적으로 결정하는 것이 아니라 프로그램 수행 시작점에서 재는 것을 말하는 것입니다. 사실 꼭 inline asm을 쓸 필요가 있는 것도 아닙니다. 단지 그게 편할 뿐이죠. 그리고 제가 기억하기로 stack size를 링크 타임에도 결정할 수 있을 텐데...아닌가요?

Quote:
stack overflow 는 상당히 쉽게 일어날 수 있습니다. 예를 들어, 재귀의
깊이가 결코 깊지 않더라도 한번 호출되는 함수에서 사용하는 스택의 양이
적지 않을 경우에는 낮은 깊이의 재귀 호출에서도 overflow 가 발생합니다.

그건 약간 다른 문제가 아닌가 싶군요. 그게 이유라면 모든 function에서 stack overflow의 가능성이 있습니다. 그게 걱정된다면 그냥 function에서 heap을 쓰면 간단한 일입니다. depth에 의해 발생하는 것이 아닌 stack overflow는 재귀 호출을 피해야할 이유가 되지 못합니다.

Quote:
또한, 일례로 AI 분야에서 개발된 탐색 알고리즘을 프로그램 개발에 적용할
때도 문제의 규모와 초기 상태에 따라 재귀의 깊이가 상상을 초월할 수
있습니다.

AI나 게임 알고리즘의 경우는 엄청난 depth가 있는 경우가 있습니다. 저도 그런 경우는 비재귀 변환을 부분적으로 쓰는 것이 나쁘지 않다고 생각합니다. 하지만 그런 부분이 오히려 특수한 부분이죠. 그런데 님은 C언어라는 틀에서 재귀에 비해 비재귀가 낫다고 주장하시는 것이기에 전 거기에 반대하는 것입니다.

차이를 쉽게 비교하자면 님은 C언어에서는 80% 이상을 비재귀로 해야한다고 주장하시는 거라면 저는 90% 이상을 재귀를 그냥 써야한다고 주장하는 것입니다. 그 근거로, 구현 속도가 빠르고 이해하기 쉬우며 실제 function call의 depth에 의한 stack overflow가 일어나는 경우는 버그로 인한 무한 루프 외에는 극히 드물고, 정 stack overflow가 의심되는 경우에는 재귀 호출을 하면서도 예방할 방법이 다각도로 존재한다는 점을 들었습니다. 물론 stack overflow를 exception으로 처리해주는 언어라면 말할 것도 없겠죠.

전웅의 이미지

creativeidler wrote:
Quote:
그 max 를 정적으로 미리 결정하기가 쉽지 않다는 것입니다.

Quote:
차이는 이식성에 있습니다. 스택을 이용해 비재귀로 구현할 경우에는
프로그램의 이식성에 주는 영향이 전혀 없지만, 인라인 어셈블리어를
사용해 해당 프로세스에 할당된 실직적인 스택 크기를 구하고 현재 함수가
사용하는 스택의 깊이를 추적하는 일은 지극히 환경 의존적인 일입니다.

정적으로 결정하는 것이 아니라 프로그램 수행 시작점에서 재는 것을 말하는 것입니다. 사실 꼭 inline asm을 쓸 필요가 있는 것도 아닙니다. 단지 그게 편할 뿐이죠.

신기한 이야기입니다. 어떻게 C 프로그램이 inline asm 도 쓰지 않고
비재귀 방식으로 변환한 것처럼 이식성의 손상도 없이 허용되는 재귀
호출의 깊이를 미리 예측할 수 있을까요? 저는 이 이유 때문에 재귀를
비재귀로 바꾸자고 주장하고 있는 것입니다.

creativeidler wrote:
Quote:
stack overflow 는 상당히 쉽게 일어날 수 있습니다. 예를 들어, 재귀의
깊이가 결코 깊지 않더라도 한번 호출되는 함수에서 사용하는 스택의 양이
적지 않을 경우에는 낮은 깊이의 재귀 호출에서도 overflow 가 발생합니다.

그건 약간 다른 문제가 아닌가 싶군요. 그게 이유라면 모든 function에서 stack overflow의 가능성이 있습니다. 그게 걱정된다면 그냥 function에서 heap을 쓰면 간단한 일입니다. depth에 의해 발생하는 것이 아닌 stack overflow는 재귀 호출을 피해야할 이유가 되지 못합니다.

재귀 호출의 깊이만이 stack overflow 의 critical factor 가 아니라는
뜻입니다. 다시 말해, 재귀 호출의 깊이 만으로 stack overflow 의
위험성을 고려하는 것은 반쪽 짜리 방법이라는 뜻이었습니다. 이 역시
지극히 재미없는 원론적인 이야기일 뿐입니다.

creativeidler wrote:
AI나 게임 알고리즘의 경우는 엄청난 depth가 있는 경우가 있습니다. 저도 그런 경우는 비재귀 변환을 부분적으로 쓰는 것이 나쁘지 않다고 생각합니다. 하지만 그런 부분이 오히려 특수한 부분이죠. 그런데 님은 C언어라는 틀에서 재귀에 비해 비재귀가 낫다고 주장하시는 것이기에 전 거기에 반대하는 것입니다.

차이를 쉽게 비교하자면 님은 C언어에서는 80% 이상을 비재귀로 해야한다고 주장하시는 거라면 저는 90% 이상을 재귀를 그냥 써야한다고 주장하는 것입니다. 그 근거로, 구현 속도가 빠르고 이해하기 쉬우며 실제 function call의 depth에 의한 stack overflow가 일어나는 경우는 버그로 인한 무한 루프 외에는 극히 드물고, 정 stack overflow가 의심되는 경우에는 재귀 호출을 하면서도 예방할 방법이 다각도로 존재한다는 것입니다. 물론 stack overflow를 exception으로 처리해주는 언어라면 말할 것도 없겠죠.

C 언어라는 틀에서는 일단 "stack overflow 를 exception 으로 처리해주는
언어" 라는 가정은 배제됩니다.

그리고, 제가 말씀드린 것은 80%, 90% 같은 정량적인 접근이 아니라
프로그램의 안정성을 보장할 수 있느냐 없느냐의 원칙적인 접근입니다.

정리하자면, 님이나 저나 많은 부분에서 같은 이야기를 하고 있는 것에
지나지 않습니다. 즉, 님께서는 일반적으로 생각하는 것보다 많은 경우에
stack overflow 의 위험성은 크지 않다. 따라서 (결국, stack overflow 의
위험성이 배제되는 경우에) 재귀 호출을 써도 무방하다는 주장을 하고 계신
것이고, 저는 stack overflow 의 위험성이 염려되면 재귀를 비재귀로
바꾸는 것이 좋다라는 주장을 하고 있는 것입니다.

이 두 주장의 차이는 저는 최소한 재귀-비재귀 변환처럼 이식성을
유지하면서 stack overflow 를 예방할 다른 방법을 찾기 어렵다고 주장하고
있는 반면, 님께서는 뭔가 알 수 없는 정체 불명의 방법으로 stack
overflow 가 의심되는 상황에서조차 재귀호출을 유지하면서 예방을 할 수
있다고 주장하고 계신 것입니다.

이제 서로의 논점을 충분히 정리했다면, 그 비법에 대한 기술적인 이야기로
논점을 옮겨 갔으면 합니다.

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

전웅의 이미지

creativeidler wrote:
Quote:
그 max 를 정적으로 미리 결정하기가 쉽지 않다는 것입니다.

Quote:
차이는 이식성에 있습니다. 스택을 이용해 비재귀로 구현할 경우에는
프로그램의 이식성에 주는 영향이 전혀 없지만, 인라인 어셈블리어를
사용해 해당 프로세스에 할당된 실직적인 스택 크기를 구하고 현재 함수가
사용하는 스택의 깊이를 추적하는 일은 지극히 환경 의존적인 일입니다.

정적으로 결정하는 것이 아니라 프로그램 수행 시작점에서 재는 것을 말하는 것입니다. 사실 꼭 inline asm을 쓸 필요가 있는 것도 아닙니다. 단지 그게 편할 뿐이죠. 그리고 제가 기억하기로 stack size를 링크 타임에도 결정할 수 있을 텐데...아닌가요?

제가 글을 인용해 답을 작성하고 있는 동안 글이 수정되었군요. 위의
답변은 수정 전 글에 대한 답변입니다.

실제로 링크시 뿐만 아니라 쉘을 통해서도 stack size 를 설정할 수
있습니다. 문제는 stack size 에 대한 설정을 완화할 수 있는 방법 자체가
프로그램 외적인 방법이고, 이 역시 inline asm 못지 않게 이식성을 갖지
않는 방법이라는 것입니다.

기계적인 방법을 통해 재귀 호출을 비재귀 형태로 변환하고, 동적 메모리
할당에 대한 지극히 관례적인 처리만 해준다면, inline asm 이나 프로그램
외적인 설정 없이도 표준 C 언어의 테두리 안에서 stack overflow 를
철저히 방지할 수 있습니다. 충분히 아름다운 방법 아닌지요?

일례로 재귀호출 방식을 비재귀로 변환함으로써 발생할 수 있는 가독성이나
유지 보수 문제는 사용된 재귀 알고리즘을 추상적으로 주석이나 문서에
기록함으로써 어느 정도 보완될 수 있다고 생각합니다 - 실제로 제가
프로그램을 작성할 때는 그렇게 하고 있습니다.

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

creativeidler의 이미지

비법? 그냥 getrlimit 쓰면 되는 거 아닌가요? 그렇게 말씀하시니 제가 착각하고 있나 하는 생각까지 듭니다만...

그리고, 찾아보니까 링크 타임에 stack size를 결정할 수 있는 게 맞더군요. 그렇다면 굳이 재보지 않아도 되는 일이라 여겨집니다만? Makefile에서 결정할 수 있는 문제이니만큼 이식성 문제는 아니죠.

Quote:

재귀 호출의 깊이만이 stack overflow 의 critical factor 가 아니라는
뜻입니다. 다시 말해, 재귀 호출의 깊이 만으로 stack overflow 의
위험성을 고려하는 것은 반쪽 짜리 방법이라는 뜻이었습니다. 이 역시
지극히 재미없는 원론적인 이야기일 뿐입니다.

depth 외에는 비재귀 호출로 변환하지 않더라도 얼마든지 피해갈 수 있다는 뜻에서 한 말입니다. 그리고 실제로 stack overflow가 날 정도의 작업이었다면 처음부터 heap을 썼어야할 일이기도 하죠.

Quote:
정리하자면, 님이나 저나 많은 부분에서 같은 이야기를 하고 있는 것에
지나지 않습니다. 즉, 님께서는 일반적으로 생각하는 것보다 많은 경우에
stack overflow 의 위험성은 크지 않다. 따라서 (결국, stack overflow 의
위험성이 배제되는 경우에) 재귀 호출을 써도 무방하다는 주장을 하고 계신
것이고, 저는 stack overflow 의 위험성이 염려되면 재귀를 비재귀로
바꾸는 것이 좋다라는 주장을 하고 있는 것입니다.

이 문제를 원칙적인 접근이라고 말씀하시지만 그 원칙이라는 것은 안정성일 텐데 대부분의 경우 재귀호출을 써도 그 안정성이라는 원칙이 훼손되지 않는다면 비재귀를 권장할 이유가 없죠. 어쨋든 지금 상황이 C 초보라고 하시는 분의 질문에 권고사항을 내야하는 것이라고 본다면 특수한 경우를 들어 비생산적인 코딩 방식을 권장하는 것보다 대부분의 경우 안정성의 훼손이 없으면서 쉬운 코딩을 권장하는 것이 올바른 권고사항일 것입니다. 정도의 문제를 따져야하는 것은 그 때문입니다.

거듭 말씀드리지만 재귀호출을 써도 안정성은 얼마든지 보장할 수 있습니다. 실제로 MySQL 등의 오픈소스 DB의 코드를 보시면 아시겠지만 재귀호출 무진장 많이 사용됩니다. 그래도 stack overflow 안 납니다.

honestee의 이미지

재귀로 만드는 게 훨신 유지보수가 쉽고, 가독성도 뛰어납니다.
tree나 graph를 구현했을 때, recursive로 만들지 않으면(물론, 가능하다고 생각하지만) 복잡도가 올라가기 때문에 저라면 비재귀로 만드는 것은 추천하지 않겠습니다.

익명 사용자의 이미지

creativeidler wrote:
비법? 그냥 getrlimit 쓰면 되는 거 아닌가요? 그렇게 말씀하시니 제가 착각하고 있나 하는 생각까지 듭니다만...

그리고, 찾아보니까 링크 타임에 stack size를 결정할 수 있는 게 맞더군요. 그렇다면 굳이 재보지 않아도 되는 일이라 여겨집니다만? Makefile에서 결정할 수 있는 문제이니만큼 이식성 문제는 아니죠.

get/setrlimit 를 사용하는 것과 실행시나 링크시에 stack size 를
설정하는 것보다 프로그램 내에서 비재귀 반복 형태의 구현을 통해 stack
overflow 를 감지하는 것이 "훨씬" 더 이식성이 있는 형태입니다.

- 링크 혹은 실행시에 stack size 를 결정할 수 있다.
- get/setrlimit 함수의 지원을 받을 수 있다.

는 것 자체가 프로그램이 의존해야 하는 가정을 추가하는 것이며, 이는
"표준 C 언어"나 POSIX 등의 충분히 의존할 수 있는 표준의 보장을 받지
못하는 것들입니다. 물론, "난 내 프로그램의 실행 환경을 내가 개발한
환경 혹은 그와 유사한 환경으로 제한해도 좋다" 라고 말씀하신다면 이는
더 고려 대상이 되지 않습니다. 그와 같은 태도라면 설명서에 "이
프로그램은 프로세스의 스택 크기가 xxxx bytes 이상인 환경에서만 정상
동작할 수 있습니다." 라는 문구를 넣는 것과 다르지 않다고 봅니다.

더구나 stack overflow 가 염려스러운 상황이라서 getrlimit 를 통해 스택
크기를 구해 실제 재귀 호출을 진행하면서 스택 사용량을 보수적으로
계산하고 있다고 가정해 보겠습니다 - 실제 함수 calling convention 을
고려해서 이를 정확하게 계산하는 것이 쉬운 문제는 아닙니다. 이제 2000번
정도의 재귀 호출이 이루어지다가 다음 번 호출에서 스택 고갈 가능성이
있음을 알았습니다. 이제 어떻게 다시 원래 상태로 복귀하시겠습니까?

- 매번 오류 값을 반환하면서 2000번의 재귀를 거스른다.
- 혹은 애초부터 stack overflow 를 signal 로 잡아내어 처리한다 (이는
프로그램에 불필요하게 또 다른 이식성 없는 부분을 넣게 됩니다).
- non-local jump 를 사용해 복귀한다 (이 역시 프로그램 내에 또 다른
비이식성을 담게 됩니다).

반면, 비재귀 반복 형태를 사용할 경우, 한번의 break 문과 스택 메모리
해제 만으로 원래 상태로 복귀가 가능합니다.

정말 단 한번이라도 stack overflow 에 대해 염려가 되는 상황에서 재귀
알고리즘을 C 언어로 구현해 보셨다면 이와 같은 현실적 문제를 만나보셨을
것입니다.

creativeidler wrote:
Quote:

재귀 호출의 깊이만이 stack overflow 의 critical factor 가 아니라는
뜻입니다. 다시 말해, 재귀 호출의 깊이 만으로 stack overflow 의
위험성을 고려하는 것은 반쪽 짜리 방법이라는 뜻이었습니다. 이 역시
지극히 재미없는 원론적인 이야기일 뿐입니다.

depth 외에는 비재귀 호출로 변환하지 않더라도 얼마든지 피해갈 수 있다는 뜻에서 한 말입니다. 그리고 실제로 stack overflow가 날 정도의 작업이었다면 처음부터 heap을 썼어야할 일이기도 하죠.

이 경우도 할당 이전에 할당 가능성을 타진할 수 있기 때문에 heap 을
사용한다는 뜻으로 받아들이면, 결국 앞서와 똑같은 지저분한 문제를
만나게 됩니다.

creativeidler wrote:
Quote:
정리하자면, 님이나 저나 많은 부분에서 같은 이야기를 하고 있는 것에
지나지 않습니다. 즉, 님께서는 일반적으로 생각하는 것보다 많은 경우에
stack overflow 의 위험성은 크지 않다. 따라서 (결국, stack overflow 의
위험성이 배제되는 경우에) 재귀 호출을 써도 무방하다는 주장을 하고 계신
것이고, 저는 stack overflow 의 위험성이 염려되면 재귀를 비재귀로
바꾸는 것이 좋다라는 주장을 하고 있는 것입니다.

이 문제를 원칙적인 접근이라고 말씀하시지만 그 원칙이라는 것은 안정성일 텐데 대부분의 경우 재귀호출을 써도 그 안정성이라는 원칙이 훼손되지 않는다면 비재귀를 권장할 이유가 없죠.

이미 이 부분에 대해서는 이전 글에서 충분히 말씀드렸습니다.
"안정성이라는 원칙이 훼손되지 않는다면" 무엇은 불가능하겠습니까?
제 주장은 그 안정성이 훼손되지 않는다는 사실에 대한 충분한 검증이
수반되어야 재귀 호출의 사용이 정당성을 갖는다는 것입니다. 제가
"대부분의" 경우에 재귀호출이 위험하다고 주장하고 있는 것은 아닙니다.
반면, 님은 "대부분의" 경우에 안전하다고 주장하고 계십니다. 자신이
익숙한 응용 분야마다 "대부분"이라는 개념이 충분히 달라질 수 있기
때문에 "대부분"이 얼만큼이냐에 대한 논쟁은 하고 싶지 않습니다. 이는
다소 보수적이며 방어적으로 프로그래밍을 하느냐 아니냐의 차이일 뿐이라
생각합니다.

creativeidler wrote:
어쨋든 지금 상황이 C 초보라고 하시는 분의 질문에 권고사항을 내야하는 것이라고 본다면 특수한 경우를 들어 비생산적인 코딩 방식을 권장하는 것보다 대부분의 경우 안정성의 훼손이 없으면서 쉬운 코딩을 권장하는 것이 올바른 권고사항일 것입니다. 정도의 문제를 따져야하는 것은 그 때문입니다.

네, 물론 언어를 배우는 초보에게 알려주는 것이라면 재귀적 알고리즘을
재귀적 구현으로 접근하는 것이 큰 교육적 가치를 갖는다는 사실에는
충분히 동의합니다. 하지만, 아무리 초보라고 해도 "모든" 경우에 있어서
재귀호출은 안전하니 믿고 사용하라고 설명할 수는 없다고 생각합니다.

creativeidler wrote:
거듭 말씀드리지만 재귀호출을 써도 안정성은 얼마든지 보장할 수 있습니다. 실제로 MySQL 등의 오픈소스 DB의 코드를 보시면 아시겠지만 재귀호출 무진장 많이 사용됩니다. 그래도 stack overflow 안 납니다.

MySQL 이 C 로 구현되어 있던가요? 제가 기억하기론 C++ 인 것으로
압니다만...

MySQL 인지는 잘 모르겠습니다만, 제가 알고 있는 DBMS 하나도 재귀호출을
이용해 작성되어 있으며, 그 덕분에 프로그램 설치시나 설정시에 stack
size 에 대한 설정을 필요한만큼 따로 해주도록 요구하고 있습니다.

또한, (제가 만들고 있는 장난감 컴파일러를 포함해) 일부 상용 컴파일러의
파서도 재귀 호출을 그대로 사용하고 있습니다.

하지만, 이 모든 경우는 현실적으로 극단적인 경우가 주어진다고 해도
재귀의 깊이가 깊어지지 않는다는 사실이 이론 혹은 실험적으로 보장되는
경우이며, 혹은 스택 크기 설정에 대한 책임을 사용자에게 전가하는
경우에 해당됩니다.

솔직히, 이 글을 쓰기 전에 다시 처음부터 논의를 훑어 보았습니다만,
논의가 길어지면 길어질수록 이 논의의 가치를 잘 모르겠습니다.

님의 주장을 정리하면,

- "안정성이 확보되면" 재귀를 쓰지 않을 이유가 없다.

이 주장에는 저 역시 처음부터 동의하고 있습니다.

- "대부분의" 경우에는 안정성이 확보된다.

"대부분의" 경우가 얼만큼인지에 대한 차이는 자신의 경험과 가치에 따라
달라질 수 있는 부분이기에 애초부터 논의 대상이 아닙니다.

- "stack overflow 가 염려되는 상황에서도" 굳이 비재귀로 바꾸지 말로
재귀 호출을 쓰면서 다른 방법으로 처리하라(???)

이것 역시 님의 주장이라면 이 부분에 대해서는 저는 동의하지 못합니다.
(만약 그렇지 않다면 결국 님이나 저나 태도의 차이만 있을뿐 같은
이야기를 한 것에 불관합니다.)

이제 남은 기술적 문제는 처음 말씀드렸듯이,

전웅 wrote:
이제 서로의 논점을 충분히 정리했다면, 그 비법에 대한 기술적인 이야기로
논점을 옮겨 갔으면 합니다.

가 됩니다.

기술적인 부분에 있어서는, stack overflow 가 걱정스러운 부분에는
개인적으로 POSIX 에서도 보장하지 못하는 (더구나 까다로운) 방법에
의존해 프로그램의 이식성을 낮추고 또 다른 부분에서 프로그램을 복잡하게
만드는 것보다, 다소 번거롭더라도 재귀를 반복 형태로 고치는 것이 훨씬
"바람직한" 방법이라고 생각합니다.

재귀-비재귀에 대한 이야기는 충분히 나왔다고 생각합니다. 실제
알고리즘에 대한 교과서를 보면, 재귀 방식과 반복 방식이 갖는 장단점이
충분히 나열되어 있습니다. 재귀-비재귀의 선택은 문제 상황을 파악해
프로그래머가 현명하게 선택해야 할 문제이며, "대부분이 안전하니 스택을
써라" 내지는 "대부분이 안전하지 않으니 쓰지 마라" 는 식의 논쟁은
소모적이라고 생각합니다 (더구나 전공 시험을 12시간도 남겨두지 않은
저한테는 더욱 소모적입니다).

논의를 플레임워로 만들지 않기 위해 최대한 님의 입장과 제 입장을
정리하며 글을 썼습니다. 만약, 논의가 계속 더 이어진다면 논의할 가치가
있는 기술적이며 객관적인 내용에 집중되기를 기대합니다.

익명 사용자의 이미지

creativeidler wrote:
비법? 그냥 getrlimit 쓰면 되는 거 아닌가요? 그렇게 말씀하시니 제가 착각하고 있나 하는 생각까지 듭니다만...

그리고, 찾아보니까 링크 타임에 stack size를 결정할 수 있는 게 맞더군요. 그렇다면 굳이 재보지 않아도 되는 일이라 여겨집니다만? Makefile에서 결정할 수 있는 문제이니만큼 이식성 문제는 아니죠.

get/setrlimit 를 사용하는 것과 실행시나 링크시에 stack size 를
설정하는 것보다 프로그램 내에서 비재귀 반복 형태의 구현을 통해 stack
overflow 를 감지하는 것이 "훨씬" 더 이식성이 있는 형태입니다.

- 링크 혹은 실행시에 stack size 를 결정할 수 있다.
- get/setrlimit 함수의 지원을 받을 수 있다.

는 것 자체가 프로그램이 의존해야 하는 가정을 추가하는 것이며, 이는
"표준 C 언어"나 POSIX 등의 충분히 의존할 수 있는 표준의 보장을 받지
못하는 것들입니다. 물론, "난 내 프로그램의 실행 환경을 내가 개발한
환경 혹은 그와 유사한 환경으로 제한해도 좋다" 라고 말씀하신다면 이는
더 고려 대상이 되지 않습니다. 그와 같은 태도라면 설명서에 "이
프로그램은 프로세스의 스택 크기가 xxxx bytes 이상인 환경에서만 정상
동작할 수 있습니다." 라는 문구를 넣는 것과 다르지 않다고 봅니다.

더구나 stack overflow 가 염려스러운 상황이라서 getrlimit 를 통해 스택
크기를 구해 실제 재귀 호출을 진행하면서 스택 사용량을 보수적으로
계산하고 있다고 가정해 보겠습니다 - 실제 함수 calling convention 을
고려해서 이를 정확하게 계산하는 것이 쉬운 문제는 아닙니다. 이제 2000번
정도의 재귀 호출이 이루어지다가 다음 번 호출에서 스택 고갈 가능성이
있음을 알았습니다. 이제 어떻게 다시 원래 상태로 복귀하시겠습니까?

- 매번 오류 값을 반환하면서 2000번의 재귀를 거스른다.
- 혹은 애초부터 stack overflow 를 signal 로 잡아내어 처리한다 (이는
프로그램에 불필요하게 또 다른 이식성 없는 부분을 넣게 됩니다).
- non-local jump 를 사용해 복귀한다 (이 역시 프로그램 내에 또 다른
비이식성을 담게 됩니다).

반면, 비재귀 반복 형태를 사용할 경우, 한번의 break 문과 스택 메모리
해제 만으로 원래 상태로 복귀가 가능합니다.

정말 단 한번이라도 stack overflow 에 대해 염려가 되는 상황에서 재귀
알고리즘을 C 언어로 구현해 보셨다면 이와 같은 현실적 문제를 만나보셨을
것입니다.

creativeidler wrote:
Quote:

재귀 호출의 깊이만이 stack overflow 의 critical factor 가 아니라는
뜻입니다. 다시 말해, 재귀 호출의 깊이 만으로 stack overflow 의
위험성을 고려하는 것은 반쪽 짜리 방법이라는 뜻이었습니다. 이 역시
지극히 재미없는 원론적인 이야기일 뿐입니다.

depth 외에는 비재귀 호출로 변환하지 않더라도 얼마든지 피해갈 수 있다는 뜻에서 한 말입니다. 그리고 실제로 stack overflow가 날 정도의 작업이었다면 처음부터 heap을 썼어야할 일이기도 하죠.

이 경우도 할당 이전에 할당 가능성을 타진할 수 있기 때문에 heap 을
사용한다는 뜻으로 받아들이면, 결국 앞서와 똑같은 지저분한 문제를
만나게 됩니다.

creativeidler wrote:
Quote:
정리하자면, 님이나 저나 많은 부분에서 같은 이야기를 하고 있는 것에
지나지 않습니다. 즉, 님께서는 일반적으로 생각하는 것보다 많은 경우에
stack overflow 의 위험성은 크지 않다. 따라서 (결국, stack overflow 의
위험성이 배제되는 경우에) 재귀 호출을 써도 무방하다는 주장을 하고 계신
것이고, 저는 stack overflow 의 위험성이 염려되면 재귀를 비재귀로
바꾸는 것이 좋다라는 주장을 하고 있는 것입니다.

이 문제를 원칙적인 접근이라고 말씀하시지만 그 원칙이라는 것은 안정성일 텐데 대부분의 경우 재귀호출을 써도 그 안정성이라는 원칙이 훼손되지 않는다면 비재귀를 권장할 이유가 없죠.

이미 이 부분에 대해서는 이전 글에서 충분히 말씀드렸습니다.
"안정성이라는 원칙이 훼손되지 않는다면" 무엇은 불가능하겠습니까?
제 주장은 그 안정성이 훼손되지 않는다는 사실에 대한 충분한 검증이
수반되어야 재귀 호출의 사용이 정당성을 갖는다는 것입니다. 제가
"대부분의" 경우에 재귀호출이 위험하다고 주장하고 있는 것은 아닙니다.
반면, 님은 "대부분의" 경우에 안전하다고 주장하고 계십니다. 자신이
익숙한 응용 분야마다 "대부분"이라는 개념이 충분히 달라질 수 있기
때문에 "대부분"이 얼만큼이냐에 대한 논쟁은 하고 싶지 않습니다. 이는
다소 보수적이며 방어적으로 프로그래밍을 하느냐 아니냐의 차이일 뿐이라
생각합니다.

creativeidler wrote:
어쨋든 지금 상황이 C 초보라고 하시는 분의 질문에 권고사항을 내야하는 것이라고 본다면 특수한 경우를 들어 비생산적인 코딩 방식을 권장하는 것보다 대부분의 경우 안정성의 훼손이 없으면서 쉬운 코딩을 권장하는 것이 올바른 권고사항일 것입니다. 정도의 문제를 따져야하는 것은 그 때문입니다.

네, 물론 언어를 배우는 초보에게 알려주는 것이라면 재귀적 알고리즘을
재귀적 구현으로 접근하는 것이 큰 교육적 가치를 갖는다는 사실에는
충분히 동의합니다. 하지만, 아무리 초보라고 해도 "모든" 경우에 있어서
재귀호출은 안전하니 믿고 사용하라고 설명할 수는 없다고 생각합니다.

creativeidler wrote:
거듭 말씀드리지만 재귀호출을 써도 안정성은 얼마든지 보장할 수 있습니다. 실제로 MySQL 등의 오픈소스 DB의 코드를 보시면 아시겠지만 재귀호출 무진장 많이 사용됩니다. 그래도 stack overflow 안 납니다.

MySQL 이 C 로 구현되어 있던가요? 제가 기억하기론 C++ 인 것으로
압니다만...

MySQL 인지는 잘 모르겠습니다만, 제가 알고 있는 DBMS 하나도 재귀호출을
이용해 작성되어 있으며, 그 덕분에 프로그램 설치시나 설정시에 stack
size 에 대한 설정을 필요한만큼 따로 해주도록 요구하고 있습니다.

또한, (제가 만들고 있는 장난감 컴파일러를 포함해) 일부 상용 컴파일러의
파서도 재귀 호출을 그대로 사용하고 있습니다.

하지만, 이 모든 경우는 현실적으로 극단적인 경우가 주어진다고 해도
재귀의 깊이가 깊어지지 않는다는 사실이 이론 혹은 실험적으로 보장되는
경우이며, 혹은 스택 크기 설정에 대한 책임을 사용자에게 전가하는
경우에 해당됩니다.

솔직히, 이 글을 쓰기 전에 다시 처음부터 논의를 훑어 보았습니다만,
논의가 길어지면 길어질수록 이 논의의 가치를 잘 모르겠습니다.

님의 주장을 정리하면,

- "안정성이 확보되면" 재귀를 쓰지 않을 이유가 없다.

이 주장에는 저 역시 처음부터 동의하고 있습니다.

- "대부분의" 경우에는 안정성이 확보된다.

"대부분의" 경우가 얼만큼인지에 대한 차이는 자신의 경험과 가치에 따라
달라질 수 있는 부분이기에 애초부터 논의 대상이 아닙니다.

- "stack overflow 가 염려되는 상황에서도" 굳이 비재귀로 바꾸지 말로
재귀 호출을 쓰면서 다른 방법으로 처리하라(???)

이것 역시 님의 주장이라면 이 부분에 대해서는 저는 동의하지 못합니다.
(만약 그렇지 않다면 결국 님이나 저나 태도의 차이만 있을뿐 같은
이야기를 한 것에 불관합니다.)

이제 남은 기술적 문제는 처음 말씀드렸듯이,

전웅 wrote:
이제 서로의 논점을 충분히 정리했다면, 그 비법에 대한 기술적인 이야기로
논점을 옮겨 갔으면 합니다.

가 됩니다.

기술적인 부분에 있어서는, stack overflow 가 걱정스러운 부분에는
개인적으로 POSIX 에서도 보장하지 못하는 (더구나 까다로운) 방법에
의존해 프로그램의 이식성을 낮추고 또 다른 부분에서 프로그램을 복잡하게
만드는 것보다, 다소 번거롭더라도 재귀를 반복 형태로 고치는 것이 훨씬
"바람직한" 방법이라고 생각합니다.

재귀-비재귀에 대한 이야기는 충분히 나왔다고 생각합니다. 실제
알고리즘에 대한 교과서를 보면, 재귀 방식과 반복 방식이 갖는 장단점이
충분히 나열되어 있습니다. 재귀-비재귀의 선택은 문제 상황을 파악해
프로그래머가 현명하게 선택해야 할 문제이며, "대부분이 안전하니 스택을
써라" 내지는 "대부분이 안전하지 않으니 쓰지 마라" 는 식의 논쟁은
소모적이라고 생각합니다 (더구나 전공 시험을 12시간도 남겨두지 않은
저한테는 더욱 소모적입니다).

논의를 플레임워로 만들지 않기 위해 최대한 님의 입장과 제 입장을
정리하며 글을 썼습니다. 만약, 논의가 계속 더 이어진다면 논의할 가치가
있는 기술적이며 객관적인 내용에 집중되기를 기대합니다.

전웅의 이미지

윗 글은 제가 올린 것입니다.

손님 모드가 허용되니 이런 불편이 있군요. :-(

실수로 같은 글이 2개가 포스팅되었습니다. 관리자님께서 적절히
처리해 주시기 바랍니다.

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

익명 사용자의 이미지

honestee wrote:
재귀로 만드는 게 훨신 유지보수가 쉽고, 가독성도 뛰어납니다.
tree나 graph를 구현했을 때, recursive로 만들지 않으면(물론, 가능하다고 생각하지만) 복잡도가 올라가기 때문에 저라면 비재귀로 만드는 것은 추천하지 않겠습니다.

전형적인 재귀호출의 형태입니다. :-)
(농담입니다, 심각하게 받아들이지 마시길 부탁드립니다.)

nohmad의 이미지

저라면 상황별로 다른 선택을 할 것 같습니다.

1. 개인 프로젝트: 성능보다는 깔끔하고 우아한 코드가 더 추구할 가치가 있다고 생각하니 재귀호출을 사용.
2. 회사 업무: 대게의 경우 납기일에 맞추는 것이 최우선. 그러므로 이 경우에도 조금이라도 덜 손이 가는 재귀호출 사용.
3. 내가 산 소스: 대게의 경우 소스를 볼 수 없겠지만, 철저하게 소비자의 입장에서 성능이나 안정성 면에서 조금이라도 이익인 비재귀호출로 만들어졌기를 희망.

다소 모순적이지만 둘다 필요해서 있는 것인데, 굳이 통계치까지 들먹여가며 쓰지 말라고 몰아세울 필요는 없을 것 같습니다. 쓸 곳이 없더라도 프로그래머에게 매우 기본이 되는 사항이니 알아두는 것은 확실히 도움이 되고, 또 살다보면 예외적인 상황에 처하는 경우도 많습니다. 또 압니까? 어떤 사람의 사고구조는 재귀호출을 생각해내기가 매우 어려운 대신 스택 중심의 사고는 매우 잘 되는 사람이 있을지도 모르지요. 공부하는 사람에게는 모든 가능성이 열려 있는 것이 좋다고 생각합니다.

creativeidler의 이미지

Quote:

- 링크 혹은 실행시에 stack size 를 결정할 수 있다.
- get/setrlimit 함수의 지원을 받을 수 있다.

는 것 자체가 프로그램이 의존해야 하는 가정을 추가하는 것이며, 이는
"표준 C 언어"나 POSIX 등의 충분히 의존할 수 있는 표준의 보장을 받지
못하는 것들입니다.

표준에 의거해야만 보장 받을 수 있는 것은 아니죠. getrlimit는 gcc가 있는 플랫폼에서는 다 가능한 걸로 알고 있습니다. Makefile 역시 소스의 일부입니다. 링크 타임에 결정하는 것은 충분히 이식성 있는 방법이죠. 물론 표준에 의거한 방법을 쓴다면 더 이식성이 있긴 하겠지만 이식성은 lower bound가 중요한 것입니다. C는 자바보다 이식성이 떨어지니 C가 안 좋은 언어라고 하면 뭐라고 반박하시겠습니까? 중요한 건 실제 상황에서 필요한 수준의 이식성이 확보되는 것입니다.

Quote:
"대부분의" 경우가 얼만큼인지에 대한 차이는 자신의 경험과 가치에 따라
달라질 수 있는 부분이기에 애초부터 논의 대상이 아닙니다.

정도의 문제는 주관적이니 논쟁 대상이 아니라고 말씀하시는데 전 결코 동의할 수 없습니다. 제가 대부분이라는 표현을 사용한 것은 나에게의 대부분, 혹은 님에게의 대부분을 말하는 게 아니라 전체 소프트웨어에서의 대부분을 의미한 것입니다. 이건 충분히 가부를 판가름할 수 있는 문제고 결코 주관적인 문제가 아닙니다. 그리고 앞서도 말씀드렸듯 정도의 문제가 권고의 문제가 되기 때문에 이 문제를 피해갈 수 없죠.

Quote:
MySQL 이 C 로 구현되어 있던가요? 제가 기억하기론 C++ 인 것으로
압니다만...

어쨋든 예외로 stack overflow를 피해가고 있진 않더군요.

stack overflow를 유발하는 원인은 말씀처럼 여러 가지가 있습니다. 그래서, 오히려 stack overflow가 재귀호출을 쓰지 말아야하는 이유가 되지 못한다는 것입니다. 그게 걱정된다면 우린 자동 변수도 하나도 못 쓰고 함수 호출 하나도 걱정해야합니다. 그런 상황에서 바람직한 코딩이 나오기 어렵죠.

좀더 공학적인 마인드가 필요한 것 같습니다. 계속 기술적인 논의만을 고집하고 있으신데 현업에서는 외부적인 요인이 기술적인 문제의 결정에도 많은 영향을 줍니다. 특히나 요즘처럼 time to market이 중요하고 유지보수가 중요한 때에는 가치가 낮은 부분은 과감히 무시하는 것이 중요합니다. 만약에 윈도우가 파란화면 절대 안 뜨게 만들 수 있지만 그러려면 10년이 걸린다고 한다면 어떻게 하시겠습니까?

사실 이런 마인드에서 본다면 stack overflow를 따지는 것이야말로 소모적입니다. stack overflow 나면 예외 상황으로 간주하여 에러 메시지 뿌리고 프로그램 종료하면 되는데 이런 문제 때문에 고민하느라 시간을 소비한다면 그 시간은 정말 소모적인 시간이 되는 거죠.

재귀를 비재귀로 바꾸어서 생기는 코드 이해의 문제를 주석으로 해결한다고 하셨는데 사실 이거야말로 중대한 bad smell 중 하나입니다. speculative generality이기도 하구요. stack overflow를 막는 다른 방법도 있는데 굳이 이런 bad smell을 유발하는 방법으로 stack overflow를 해결해야할 이유를 전 도저히 모르겠습니다.

dasomoli의 이미지

creativeidler wrote:
예외 상황으로 간주하여 에러 메시지 뿌리고 프로그램 종료하면 되는데

이 부분은 문제가 될 것 같네요 8)



dasomoli의 블로그(http://dasomoli.org)
dasomoli = DasomOLI = Dasom + DOLI = 다솜돌이
다솜 = 사랑하옴의 옛 고어.
Developer! ubuntu-ko! 다솜돌이 정석
creativeidler의 이미지

dasomoli wrote:
creativeidler wrote:
예외 상황으로 간주하여 에러 메시지 뿌리고 프로그램 종료하면 되는데

이 부분은 문제가 될 것 같네요 8)

저건 일종의 가정입니다. 그런 상황인데 stack overflow 때문에 bad smell을 만든다면 시간 낭비다...이런 얘기죠.

전웅의 이미지

논의가 한 페이지를 넘어갈만큼 지리해졌으니, 좀 정리를 하고
말씀드리겠습니다.

처음 제가 이 쓰레드에 포스팅을 하게 된 계기는 재귀 호출의 비재귀
구현이 일종의 편법(?)에 가까운 방법이라는 글을 보았기 때문입니다.
신기하게도 그와 매우 유사한 논의를 오래 전에 제 홈페이지 게시판에서
했었고, 그때 썼던 글이 조금이라도 도움이 될 것 같은 다음에 링크를
했습니다. 그렇게 링크된 글은

1. 재귀의 비재귀로의 전환은 항상 가능하다.

2. 재귀 알고리즘의 비재귀 구현이 편법으로 볼 만큼 부정적인 것은 아니다.

3. 비재귀 구현의 장점은 함수 오버헤드를 피하는 성능 문제 이외에도
시스템 자원에 대한 제어를 직접할 수 있다는 것이다.

4. 일반적으로 재귀 알고리즘은 재귀로 구현하는 것이 가장 자연스럽다.
그럼에도 다음과 같은 두 가지 경우에는 비재귀로 전환할 필요가 있다.
4-1. 프로그램의 성능에 치명적인 영향을 준다고 판단되는 경우
4-2. 프로그램의 안정성에 치명적인 영향을 준다고 판단되는 경우

대충 이와 같은 내용을 담고 있는 것입니다.

이때 단지 "성능"에 대한 기우 때문에 님께서 재귀를 비재귀로 구현하는
것은 불필요하다는 글을 올리셨고, 저는 재귀를 비재귀로 바꾸는 것에는
성능 뿐만 아니라 "시스템 자원의 직접 제어"라는 장점도 함께 고려되어야
한다는 글을 올렸습니다.

그리고 한참을 지나 이제 문제점은 다음 2가지로 줄여 볼 수 있다고
생각합니다.

- (저는 별로 이야기 거리로 삼고 싶지 않은) "대부분"의 프로그램이
재귀호출에 대해 안전하냐, 그렇지 않느냐의 문제

- 프로그램의 안정성에 주는 영향이 "있다고" 확인되는 경우에도 비재귀
변환을 하지 않고 재귀로 둘 것인가 하는 문제

creativeidler wrote:
Quote:

- 링크 혹은 실행시에 stack size 를 결정할 수 있다.
- get/setrlimit 함수의 지원을 받을 수 있다.

는 것 자체가 프로그램이 의존해야 하는 가정을 추가하는 것이며, 이는
"표준 C 언어"나 POSIX 등의 충분히 의존할 수 있는 표준의 보장을 받지
못하는 것들입니다.

표준에 의거해야만 보장 받을 수 있는 것은 아니죠. getrlimit는 gcc가 있는 플랫폼에서는 다 가능한 걸로 알고 있습니다. Makefile 역시 소스의 일부입니다. 링크 타임에 결정하는 것은 충분히 이식성 있는 방법이죠. 물론 표준에 의거한 방법을 쓴다면 더 이식성이 있긴 하겠지만 이식성은 lower bound가 중요한 것입니다. C는 자바보다 이식성이 떨어지니 C가 안 좋은 언어라고 하면 뭐라고 반박하시겠습니까? 중요한 건 실제 상황에서 필요한 수준의 이식성이 확보되는 것입니다.

이식성 이야기만 잘라내어 반박하고 계시지만 이식성의 문제만 있는 것은
아닙니다.

- get/setrlimit 함수를 사용할 경우, 스택 사용을 추적하는 것이 비재귀
구현을 사용하는 것보다 결코 쉽지 않습니다. 예전에 저도 제가 만든
프로그램에 frame pointer 와 stack pointer 를 추적해 다음 재귀 호출이
stack overflow 를 일으키는지를 검사해주는 함수를 만들어 사용했었으나,
실제 그 함수가 갖는 지극히 이식성 없는 부분들과 활용도의 한계에
부딪혀 없애버리고 말았습니다. 지금 당장이라도 geet/setrlimit 함수로
그와 같은 기능을 하는 함수를 만들어 보시기 바랍니다. 단지,
get/setrlimit 함수가 제공되어야 한다는 가정 이외에도 수많은 지저분한
가정에 의존하는 너덜거리는 프로그램이 된다는 것을 확인하실 수 있을
겁니다.

- 또한, (반복해서 드리는 말씀입니다만) 설사 그와 같은 함수를
성공적으로 구현해 재귀 호출의 가능성을 검사한다고 하더라도 stack
overflow 가 예측되는 상황에서 다시 재귀를 거슬러 돌아오는 것이
비재귀 구현에서 뒷정리를 하는 것보다 여러 면에서 낫지 않다는
것입니다. 이미 제가 최소한 3가지 다른 방법을 말씀드렸으나 그 3가지
모두 그렇습니다.

반면, 비재귀 방식의 경우, 재귀를 비재귀로 바꾸는 수고는 분명히 있지만,
동적 메모리 할당이라는 지극히 언어 표준의 틀 안에서 시스템 자원에 대한
관리를 할 수 있으며, 재귀 호출 모사를 진행하다가 문제가 되어 되돌리는
경우에도 breack 문 하나와 함수 호출 하나로 모든 뒷정리가 된다는 장점이
있습니다.

creativeidler wrote:
Quote:
"대부분의" 경우가 얼만큼인지에 대한 차이는 자신의 경험과 가치에 따라
달라질 수 있는 부분이기에 애초부터 논의 대상이 아닙니다.

정도의 문제는 주관적이니 논쟁 대상이 아니라고 말씀하시는데 전 결코 동의할 수 없습니다. 제가 대부분이라는 표현을 사용한 것은 나에게의 대부분, 혹은 님에게의 대부분을 말하는 게 아니라 전체 소프트웨어에서의 대부분을 의미한 것입니다. 이건 충분히 가부를 판가름할 수 있는 문제고 결코 주관적인 문제가 아닙니다. 그리고 앞서도 말씀드렸듯 정도의 문제가 권고의 문제가 되기 때문에 이 문제를 피해갈 수 없죠.

일평생 "전체 분야"의 "전체" 소프트웨어 개발에 참여하는 프로그래머가
몇이나 된다고 생각하십니까? safety-critical 분야에서 주로 개발을 하게
되는 개발자와 일반 client-side 응용 프로그램을 개발하는 개발자가
바라보는 "대부분"은 다를 수 밖에 없으며, 달라야만 합니다. 예를 들어
설명해 보겠습니다. 미국, 유럽, 일본 등의 자동차 생산 업체에서 자동차에
들어가는 코드를 개발할 때 사용하는 대표적 가이드 라인인 MISRA-C 는
재귀호출의 사용을 엄격히 "금지"하고 있습니다. 참고로 이 MISRA-C 는
자동차 업계 뿐 아니라 안전이 중요시되는 다른 분야에서도 꾸준히
채택되고 있습니다. 추가로 NASA 에서 사용하는 코드를 작성할 때 지켜야
하는 문서에도 재귀호출을 "금지"하고 있습니다. 결론적으로, 소프트웨어
"전체" 분야에서 이와 같은 코드들이 차지하는 비중이 적고, 그 탓에 재귀
호출이 프로그램의 안정성에 치명적 영향을 줄 수 있는 가능성이
줄어든다고 해서, 재귀의 비재귀 구현이 갖는 가치가 줄어드는 것은
아닙니다. 즉, 전체적으로 보았을 때 20% 확률로 문제를 일으키든 80%
확률로 문제를 일으키든, 자신이 작성하는 코드에서 0% 라면 무의미한
변환이며, 100% 라면 중요한 변환이 될 수 있는 것입니다.

이와 같은 까닭에 "대부분이" 얼만큼인지에는 전혀 관심이 없으며, 권고의
문제가 된다면 앞서 언급한 코딩 가이드 라인처럼 관점이나 분야를 좁혀
권고의 내용과 무게를 달리하면 끝날 문제입니다. 단지, 전체 소프트웨어의
20% 정도가 재귀 호출로 안정성에 문제를 가질 수 있다는 이유 때문에
MISRA-C 에서 "당신의 재귀 호출 코드는 20% 의 확률로 문제를 일으킬 수
있고, 따라서 당신이 개발한 프로그램을 탑재한 자동차는 12% 의 확률로
사고가 날 수 있습니다" 라고 권고할 수는 없는 노릇입니다. 유사하게
교육을 위한 교과서에서 기반 상황에 대한 뚜렷한 명시 없이 "재귀 호출을
힘들게 비재귀로 바꿀 필요 없이 그대로 사용해도 문제를 일으키지 않는다"
와 같은 일반적 내용을 담는 것도 부적절하다고 봅니다.

그런데도, 알 수 없는 이유로 님은 "대부분"의 구체적 논의에 대한 미련을
버리지 못하고 계신듯 합니다. :-(

다시 한번 말씀드리지만, 저는 그 "대부분"의 정량적 관점에는 전혀 관심이
없습니다. 또한, 제가 관심 없는 이유는 충분히 위에서 설명 드렸다고
생각합니다.

creativeidler wrote:
Quote:
MySQL 이 C 로 구현되어 있던가요? 제가 기억하기론 C++ 인 것으로
압니다만...

어쨋든 예외로 stack overflow를 피해가고 있진 않더군요.

MySQL 구현에 관심이 없어 들여다보지 않았습니다만, MySQL 역시
지극히 극단적인 경우에도 stack overflow 가 일어나지 않음을 이론적 혹은
실험적 방법으로 보장받고 있거나, 혹은 프로그램이 사용하는 스택 크기에
대한 설정을 사용자에게 전가하거나 하는 방법을 취하고 있다고 봅니다.

또한, 무엇보다도 악의적인 사용자에 의해 시스템 전체에 구멍을 낼 수
있는 부분에 stack overflow 가 나도록 내버려 두지는 않았을 것이라
생각합니다 - 만약, 그와 같은 문제가 보고된다면 이를 "의도하지 않은"
버그로 간주해 해결하리라 믿어 의심치 않습니다.

creativeidler wrote:
stack overflow를 유발하는 원인은 말씀처럼 여러 가지가 있습니다. 그래서, 오히려 stack overflow가 재귀호출을 쓰지 말아야하는 이유가 되지 못한다는 것입니다. 그게 걱정된다면 우린 자동 변수도 하나도 못 쓰고 함수 호출 하나도 걱정해야합니다. 그런 상황에서 바람직한 코딩이 나오기 어렵죠.

"단지 자동차의 급발진 사고가 발생할 수 있다는 이유 때문에 변속기에
안전 장치를 다느니 차라리 자동차를 타지 맙시다."

"자동차 운전자가 사망할 가능성이 있다는 이유만으로 에어백을 다느니
차라리 자동차를 타지 맙시다."

와 무엇이 다른 주장인지요? 주장의 근거로 논리적 비약을 하고 계십니다.
제 주장은 "stack overflow 때문에 재귀호출을 써서는 안 된다"가 아니라
"stack overflow 가 치명적 결과로 이어질 수 있는 경우에는 (당연히 다른
부분에서도 주의해야 하고) 재귀 호출에도 주의해야 한다" 입니다. 이 둘의
차이를 짓지 못하는 이상 더 이상의 의미있는 논의는 불가능 합니다.

creativeidler wrote:
좀더 공학적인 마인드가 필요한 것 같습니다. 계속 기술적인 논의만을 고집하고 있으신데 현업에서는 외부적인 요인이 기술적인 문제의 결정에도 많은 영향을 줍니다. 특히나 요즘처럼 time to market이 중요하고 유지보수가 중요한 때에는 가치가 낮은 부분은 과감히 무시하는 것이 중요합니다. 만약에 윈도우가 파란화면 절대 안 뜨게 만들 수 있지만 그러려면 10년이 걸린다고 한다면 어떻게 하시겠습니까?

또 한번 주장의 근거로 논리적 비약을 하고 계십니다.

creativeidler wrote:
사실 이런 마인드에서 본다면 stack overflow를 따지는 것이야말로 소모적입니다. stack overflow 나면 예외 상황으로 간주하여 에러 메시지 뿌리고 프로그램 종료하면 되는데 이런 문제 때문에 고민하느라 시간을 소비한다면 그 시간은 정말 소모적인 시간이 되는 거죠.

그와 같은 문제 때문에 고민해야 하는 경우도 있다는 것이 제 주장의
요지입니다. 즉, "항상" 그런 고민을 해야 한다는 주장도 일반화의
오류이지만, 그런 고민을 하는 것은 "항상" 시간 낭비라는 주장도 일반화의
오류입니다.

creativeidler wrote:
재귀를 비재귀로 바꾸어서 생기는 코드 이해의 문제를 주석으로 해결한다고 하셨는데 사실 이거야말로 중대한 bad smell 중 하나입니다. speculative generality이기도 하구요. stack overflow를 막는 다른 방법도 있는데 굳이 이런 bad smell을 유발하는 방법으로 stack overflow를 해결해야할 이유를 전 도저히 모르겠습니다.

저나 님이나 자신의 생각에 확고함이 있는 상태에서 이미 논의가 서로를
설득하는 목적을 가지고 있다고는 생각하지 않습니다.

또한, 처음 링크한 글에서부터 마지막 글까지 재귀호출이 갖는 유용성과
가치를 무시한 적 없으며, 제가 강조하고 싶은 부분은 재귀적 구현과
비재귀적 구현 사이의 trade-off 가 필요하며, 그 기준으로 빼놓지 말아야
하는 요소 중에 하나가 재귀호출 결과로 프로그램의 안정성에 손상이 생길
수 있는지 또 그 손상이 얼마나 치명적일 수 있는지라는 것입니다.

다른 부분에 대한 논의를 또 다시 반복할 필요 없이, 님과 제 주장의
유일한 차이는, 님은 저와 달리 "그와 같은 문제가 될 수 있는 상황에서도
재귀 호출을 유지해야 한다" 는 주장을 하고 계신 것입니다. 다르게
표현하면, 비재귀의 장점이 빛을 발할 수 있는 순간에도 비재귀의 *dark
side* 만을 끄집어 내어 비재귀가 갖는 상대적 장점을 평가절하하고
계신다는 생각마져 듭니다.

이는 아마도 애초부터 재귀 호출의 실패가 치명적인 결과로 이어질 수 있는
분야에서 개발을 하지 않으시기 때문에 경험의 차이로 재귀 호출을
바라보는 태도에도 차이가 생긴 것은 아닐까 생각합니다.

이미 재귀-비재귀와 관련해서 당장 머리에서 끄집어 낼 수 있는 지식은 다
꺼낸 것 같습니다. 이제 시험이 끝나 :-) 밀린 일 진도를 따라잡을
시간이라 :-( 제 생각은 여기서 정리하려 합니다.

재귀-비재귀에 대한 평소 생각을 명확하게 정리할 수 있는 유익한
논의였습니다.

그럼...

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

creativeidler의 이미지

Quote:
이식성 이야기만 잘라내어 반박하고 계시지만 이식성의 문제만 있는 것은
아닙니다.

일부분을 반박하는 것을 "잘라내어"와 같은 방식으로 표현하는 것은 좀 유감이군요. 오히려 님이 제 해결책 중 getrlimit만 잘라내어 반박하고 있으신 것은 아닌지 생각해보시죠.

Quote:
get/setrlimit 함수가 제공되어야 한다는 가정 이외에도 수많은 지저분한
가정에 의존하는 너덜거리는 프로그램이 된다는 것을 확인하실 수 있을
겁니다.

비재귀로 인한 bad smell과 환경적인 제어 중 어느 것이 더 너덜거리는 것인지는 쉽게 말할 수 있는 문제가 아닐 텐데요.

Quote:
일평생 "전체 분야"의 "전체" 소프트웨어 개발에 참여하는 프로그래머가
몇이나 된다고 생각하십니까?

님은 성능상 문제가 없고 재귀호출 깊이가 깊지 않다면 거의 항상 비재귀가 낫다는 논리를 제시하지 않으셨습니까? 이것은 님이 의도했듯 아니든 이미 일반론입니다. 그에 대한 저의 답은 이것은 application specific한 문제이며 대부분은 이런 부분을 고려할 필요가 없다는 것을 말하고 있는 것이구요.

이런 정도의 문제에 대한 논의에 관심이 없으시다면 님의 일반론에 가까운 비재귀호출 우월성 주장은 철회하셔야 할 것 같은데요. mission critical한 분야에 한해 비재귀 호출이 유리할 수 있다.. 정도로 주장하셨다면 제가 왜 동의하지 않았겠습니까?

Quote:
미국, 유럽, 일본 등의 자동차 생산 업체에서 자동차에
들어가는 코드를 개발할 때 사용하는 대표적 가이드 라인인 MISRA-C 는
재귀호출의 사용을 엄격히 "금지"하고 있습니다.

초기에 전 PC에서의 프로그램이라고 제한한 바 있는 것 같은데요.

Quote:
"단지 자동차의 급발진 사고가 발생할 수 있다는 이유 때문에 변속기에
안전 장치를 다느니 차라리 자동차를 타지 맙시다."

"자동차 운전자가 사망할 가능성이 있다는 이유만으로 에어백을 다느니
차라리 자동차를 타지 맙시다."


전 비유에 대단히 관대한 편입니다만 이 비유는 아무리해도 제 주장과 잘 대응이 안되는군요. 제 주장을 잘못 이해하신 것 아닌가요? 제 주장은 stack overflow를 유발하는 원인은 재귀 호출 뿐 아니라 모든 함수 호출과 자동 변수의 사용 등이 될 수 있는데 stack overflow를 이유로 재귀 호출만 딱 막겠다는 주장이 얼마다 설득력이 있느냐 하는 것입니다. 굳이 자동차 비유로 가자면 충돌 시 운전자의 안전성을 확보하려면 범퍼도 있어야하고 에어백도 있어야하고 전반부의 탄성도 좋아야하는데 왜 에어백만 하나 달랑 설치하고 범퍼는 그 모양으로 두느냐...정도로 할 수 있겠죠.

Quote:
그와 같은 문제 때문에 고민해야 하는 경우도 있다는 것이 제 주장의
요지입니다. 즉, "항상" 그런 고민을 해야 한다는 주장도 일반화의
오류이지만, 그런 고민을 하는 것은 "항상" 시간 낭비라는 주장도 일반화의
오류입니다.

위에 다른 분의 댓글을 보고 이런 얘기가 나올 거란 생각이 들어 부연 설명을 해두었습니다.

Quote:
또 한번 주장의 근거로 논리적 비약을 하고 계십니다.

이런 말씀을 하실 땐 왜 비약인지를 설명할 의무 같은 게 있다고 생각하는데요. 님의 안정성 절대론(?)에 대해 생산성을 위해 안정성을 희생하는 것도 얼마든지 가능하다는 주장을 한 것이 왜 비약인지요?

Quote:

이는 아마도 애초부터 재귀 호출의 실패가 치명적인 결과로 이어질 수 있는
분야에서 개발을 하지 않으시기 때문에 경험의 차이로 재귀 호출을
바라보는 태도에도 차이가 생긴 것은 아닐까 생각합니다.

아직 학생이신 것 같은데 경험을 이야기할 정도로 많은 경험을 갖고 있으신가요? 저도 학생 수준의 경험이라면 어느 정도 mission critical한 분야에 대한 경험이 적지 않게 있답니다.

전반적으로 님은 스스로가 일반론을 주장했다는 사실을 잘 인지하지 못하고 있으신 것 같습니다. 그래서 저의 일반론적 반론에 대해 이런 식의 반론을 하고 있으신 게 아닌가 싶군요. 처음 몇 번의 자신의 글을 다시 읽어보시는 것이 어떻겠습니까?

전웅의 이미지

creativeidler wrote:
Quote:
이식성 이야기만 잘라내어 반박하고 계시지만 이식성의 문제만 있는 것은
아닙니다.

일부분을 반박하는 것을 "잘라내어"와 같은 방식으로 표현하는 것은 좀 유감이군요.

이는 님의 이전 답글에서 제가 stack overflow 에 대한 비재귀 접근이 아닌
예방책이나 혹은 재귀 호출에서 복귀할 때 발생할 수 있는 문제에 대한
기술적 지적을 한 부분에 대해서는 간단히 생략해버리고 이식성에 대해
언급한 부분에 대해서만 반박을 하셨다는 뜻으로 드린 말씀입니다.
"잘라내어"라는 표현에 부정적인 의도를 담으려 한 것은 아닙니다.

creativeidler wrote:
오히려 님이 제 해결책 중 getrlimit만 잘라내어 반박하고 있으신 것은 아닌지 생각해보시죠.

??? 저는 지금까지의 님의 글을 모두 인용하며 그에 대한 제 생각을 달고
있습니다.

getrlimit 이외의 해결책으로 님이 제시하신 것은 결국 프로그램 외적인
환경에서 설정을 해준다는 것이었습니다. 그리고 그에 대한 반박으로는
이는 프로그램이 또 다시 의존해야 하는 가정을 만들게 되므로 그 보다는
비재귀 전환이 프로그램 자체의 견고함을 위해 낫다고 생각한다는 것이 제
의견이었습니다. 또 다시 같은 논의를 반복할 필요는 없다고 봅니다.

그리고 사용해 보시면 아시겠지만, getrlimit 만으로 근본적 해결이 되지
않습니다. 결국, 프로그램 외적인 환경 설정에 의존하는 방법이나 부분적인
해결 방법만을 나열해 놓으신 상태에서 각각의 단점을 지적하고 제 생각을
말씀드렸는데도 getrlimit 만 잘라내어 반박하고 있다는 말씀을 어떻게
이해해야 할지 모르겠군요.

creativeidler wrote:
Quote:
get/setrlimit 함수가 제공되어야 한다는 가정 이외에도 수많은 지저분한
가정에 의존하는 너덜거리는 프로그램이 된다는 것을 확인하실 수 있을
겁니다.

비재귀로 인한 bad smell과 환경적인 제어 중 어느 것이 더 너덜거리는 것인지는 쉽게 말할 수 있는 문제가 아닐 텐데요.

제가 환경적인 제어 vs. 비재귀 접근을 비교했습니까? 아니면 (이미 인용한
부분에서 명백하게 보이듯이) getrlimit 함수를 사용한 방법 vs. 비재귀
접근을 비교했습니까?

환경적인 제어는 분명 비재귀 접근에 비해 보다 깔끔한 형태를 갖습니다.
하지만, 프로그램에 대한 제 기본적인 생각은 가급적 문제를 프로그램
외부로 전가하지 말자는 것이며, 이런 개인적인 생각에 따라 비재귀가
환경적 제어보다 낫다고 생각하는 바입니다. 반대로 님께서는 비재귀가
풍기는 bad smell 때문에 환경적인 제어를 선택하겠다고 말씀하고
계십니다. 이 부분에 대해서 둘 사이의 합의점을 찾아야 하는지요? 저와
님이 같은 프로젝트를 진행하고 있지 않은 이상 그럴 필요는 없다고
봅니다.

creativeidler wrote:
Quote:
일평생 "전체 분야"의 "전체" 소프트웨어 개발에 참여하는 프로그래머가
몇이나 된다고 생각하십니까?

님은 성능상 문제가 없고 재귀호출 깊이가 깊지 않다면 거의 항상 비재귀가 낫다는 논리를 제시하지 않으셨습니까?

제 글을 좀 더 신중하게 읽어주시기를 부탁드립니다. 제가 처음 링크했던
글에서 인용합니다.

전웅 wrote:
재귀적 구현을 그대로 남겨 놓은 경우는 가능한 재귀 호출의 깊이가 지극히 얕고, 프로그램의 전체 속도에 크게 영향을 주지 않는 부분일 경우로 제한되어야 한다

즉, 재귀 호출의 깊이가 낮고 (따라서 프로그램의 안정성에 주는 영향이
미미하고), 프로그램의 전체 속도에 크게 영향을 주지 않는 경우에는
재귀적 구현을 그대로 남겨 놓아도 무방하다고 말하고 있습니다.
엉뚱하게도 님은 이 부분을

- "성능상 문제가 없고" = 프로그램의 전체 속도에 크게 영향을 주지 않고
- "재귀의 깊이가 깊지 않다면" = 재귀 호출의 깊이가 낮으면

"비재귀가 낫다"고 주장하는 것으로 받아들이고 계시는군요. 이게 오해의
근본적 이유였다면 이제 오해는 그만 푸셔도 될 것 같습니다.

creativeidler wrote:
이것은 님이 의도했듯 아니든 이미 일반론입니다. 그에 대한 저의 답은 이것은 application specific한 문제이며 대부분은 이런 부분을 고려할 필요가 없다는 것을 말하고 있는 것이구요.

이 논의 진행하면서 정리를 몇 번 하는지 모르겠습니다만, 다시 한번
정리해 보겠습니다.

A----------------------C---------------------------B

A: 성능에 대한 영향이 극단적으로 크거나 혹은 프로그램의 안정성에 매우
치명적인 경우
B: 성능에 주는 영향이 극단적으로 미미하거나 혹은 프로그램의 안정성에
거의 영향을 주지 않는 경우

일반적으로 A 에는 비재귀, B 에는 재귀를 두는 것에 동의할 것입니다.
이는 많은 사람들이 외치는 "recursion wins in some cases, iteration
wins in other cases" 라는 말이 극단적으로 적용될 수 있는 경우입니다.
이제 문제는 어중간한 C 부분입니다. C 부분에서 많은 프로그래머는 재귀적
접근이 주는 가독성 및 유지 보수성과 성능이나 안정성이라는 다른 요소를
trade-off 하게 될 것입니다. 이때 님은 C 와 같은 경우에는 일반적으로
재귀를 쓰는 것에 문제가 없다는 쪽이고, 저는 비재귀로 바꾸는 것이
낫다는 쪽입니다.

그리고 이 두 선택은 더 이상 제가 님을 설득하고, 님이 저를 설득할
문제가 아니라고 봅니다. 그리고, 설사 님이나 제가 설득 당했다고 해서,
다른 프로그래머들에게 직접적 영향을 주는 사안도 아니라고 봅니다. 이전
글에서, 또 그전 글에서 말씀드렸듯이 이는 해당 문제에 직면한
프로그래머가 선택할 문제이며, 단지 누군가가 C 라는 경우에 재귀를
선호한다고 해서, 혹은 비재귀를 선호한다고 해서 문제가 되지는 않는다고
봅니다.

그럼에도 님은 제가 C 와 같은 경우에 비재귀를 선호하는 것이 지극히
못마땅하신 것 같습니다. :-(

그리고, 이전 글에서, 또 다시 그전 글에서 말씀드렸듯이 제가 님의 의견에
동의하지 못하는 부분은 A 와 같은 경우에도 재귀를 그대로 두는 것이
낫다고 주장하신 부분입니다. 이를 확인하기 위해 제가 드렸던 말씀을
인용합니다.

전웅 wrote:
- "stack overflow 가 염려되는 상황에서도" 굳이 비재귀로 바꾸지 말로
재귀 호출을 쓰면서 다른 방법으로 처리하라(???)

이것 역시 님의 주장이라면 이 부분에 대해서는 저는 동의하지 못합니다.
(만약 그렇지 않다면 결국 님이나 저나 태도의 차이만 있을뿐 같은
이야기를 한 것에 불관합니다.)

전웅 wrote:
다른 부분에 대한 논의를 또 다시 반복할 필요 없이, 님과 제 주장의
유일한 차이는, 님은 저와 달리 "그와 같은 문제가 될 수 있는 상황에서도
재귀 호출을 유지해야 한다" 는 주장을 하고 계신 것입니다.

그런데, 이제는 또 다음과 같은 말씀을 하시는군요.

creativeidler wrote:
mission critical한 분야에 한해 비재귀 호출이 유리할 수 있다.. 정도로 주장하셨다면 제가 왜 동의하지 않았겠습니까?

논의 과정에서 서로의 의견에 조금이라도 오해가 있으면, 논의가 진행되는
과정에서 이 오해가 부풀어 문제가 될 수 있습니다. 이번 글을 통해 님이
말씀하고자 하시는 바를 대충이나마 정리할 수 있었습니다. 이는 이 글의
마지막 부분에서 말씀드리겠습니다.

creativeidler wrote:
Quote:
미국, 유럽, 일본 등의 자동차 생산 업체에서 자동차에
들어가는 코드를 개발할 때 사용하는 대표적 가이드 라인인 MISRA-C 는
재귀호출의 사용을 엄격히 "금지"하고 있습니다.

초기에 전 PC에서의 프로그램이라고 제한한 바 있는 것 같은데요.

PC 에서도 프로그램 오류의 결과가 치명적인 분야는 많습니다. 상용
프로그램이 "segmentation fault" 를 내며 사용자 자료를 모두 날리고
종료해 버리는 것도 프로그램 오류의 결과가 치명적인 경우로 보기에
충분합니다. 제가 일례라고 분명히 밝혔듯이, 이는 그와 같은 경우의
구체적 예를 든 것 뿐입니다.

creativeidler wrote:
Quote:
"단지 자동차의 급발진 사고가 발생할 수 있다는 이유 때문에 변속기에
안전 장치를 다느니 차라리 자동차를 타지 맙시다."

"자동차 운전자가 사망할 가능성이 있다는 이유만으로 에어백을 다느니
차라리 자동차를 타지 맙시다."


전 비유에 대단히 관대한 편입니다만 이 비유는 아무리해도 제 주장과 잘 대응이 안되는군요. 제 주장을 잘못 이해하신 것 아닌가요? 제 주장은 stack overflow를 유발하는 원인은 재귀 호출 뿐 아니라 모든 함수 호출과 자동 변수의 사용 등이 될 수 있는데 stack overflow를 이유로 재귀 호출만 딱 막겠다는 주장이 얼마다 설득력이 있느냐 하는 것입니다. 굳이 자동차 비유로 가자면 충돌 시 운전자의 안전성을 확보하려면 범퍼도 있어야하고 에어백도 있어야하고 전반부의 탄성도 좋아야하는데 왜 에어백만 하나 달랑 설치하고 범퍼는 그 모양으로 두느냐...정도로 할 수 있겠죠.

제가 언제 재귀 호출"만" 막겠다고 주장했는지요? 존재하지도 않는 주장을
반박하실 필요는 없습니다.

이미 이전 글에서 말씀드렸듯이, 범퍼, 전반부 탄성, 좋은 제동력 등이
있어도 에어백이 없으면 운전자가 위험할 수 있다는 말씀을 드리고 있는
것입니다.

제 글에 무슨 문제가 있습니까? 왜 자꾸 제 주장을 보고 싶으신대로만 보고
계신지 모르겠습니다. 몇번 반복해 표현을 달리해가며 말씀드리고 있음에도
님은 님이 반박하고자 하는 없는 내용을 넣어 반박하고 계시는군요.

제가 "포인터는 invalid storage reference 를 일으킬 수 있으니 주의해
사용하라" 라고 주장하면, 이는 안정성과 관련된 프로그램의 다른 부분은
다 무시하고 포인터만 조심하라고 주장하는 것인지요?

creativeidler wrote:
Quote:
또 한번 주장의 근거로 논리적 비약을 하고 계십니다.

이런 말씀을 하실 땐 왜 비약인지를 설명할 의무 같은 게 있다고 생각하는데요. 님의 안정성 절대론(?)에 대해 생산성을 위해 안정성을 희생하는 것도 얼마든지 가능하다는 주장을 한 것이 왜 비약인지요?

"주장의 근거로"라는 표현을 사용했듯이 님의 주장을 뒷받침하는 근거로
사용된 "예"가 비약이라는 뜻이었습니다. 님의 "주장"이 논리적 비약이라는
뜻이 아닙니다.

그리고, 다른이의 주장에 함부로 "절대론" 이라는 이름을 붙이는 것이 별로
바람직하지는 않다고 생각합니다. 제가 님의 주장을 "생산성 절대론"
이라고 부른다면 이에 흔쾌히 동의하시겠습니까?

creativeidler wrote:
Quote:

이는 아마도 애초부터 재귀 호출의 실패가 치명적인 결과로 이어질 수 있는
분야에서 개발을 하지 않으시기 때문에 경험의 차이로 재귀 호출을
바라보는 태도에도 차이가 생긴 것은 아닐까 생각합니다.

아직 학생이신 것 같은데 경험을 이야기할 정도로 많은 경험을 갖고 있으신가요? 저도 학생 수준의 경험이라면 어느 정도 mission critical한 분야에 대한 경험이 적지 않게 있답니다.

지금까지 제가 본 논의 글 중에 가장 수준 낮은 내용입니다. 이런 식의
표현으로 전체 논의의 질을 떨어뜨리지 않으셨으면 좋겠습니다. 그럼, 제가
학생이다보니 할 일이 없어서 MISRA-C 를 교양 서적처럼 읽어봤다고
생각하십니까?

제가 님의 경험 분야가 다르다고 파악한 이유는, stack overflow 감지를
위해 getrlimit 라는 정말 비현실적인 방법을 말씀하셨기 때문입니다. 단
한번이라고 그 함수를 혹은 그와 근본적으로 유사한 방법을 통해 재귀
호출의 stack overflow 를 막으려고 해보셨다면 그 방법이 왜 프로그램을
"너덜너덜"하게 만드는 방법인지 아셨으리라 믿습니다. 그래서 내릴 수
있었던 제 결론은, 님께서 주로 참여하시는 개발 분야가 재귀 호출이 갖는
가독성과 유지 보수성이 더 가치를 발하는 분야라고 파악한 것입니다.

creativeidler wrote:
전반적으로 님은 스스로가 일반론을 주장했다는 사실을 잘 인지하지 못하고 있으신 것 같습니다. 그래서 저의 일반론적 반론에 대해 이런 식의 반론을 하고 있으신 게 아닌가 싶군요. 처음 몇 번의 자신의 글을 다시 읽어보시는 것이 어떻겠습니까?

이제 정말 마지막으로 정리를 해보겠습니다. 이미 위에서 선까지 그려가며
말씀드렸지만, 님께서 주장하시는 바는

"일반적으로 비재귀 변환보다 재귀 호출이 갖는 이득이 생산성 측면에서
우월하다. 따라서 뚜렷한 근거 없이 재귀를 무조건 비재귀로 바꾸라 말하는
일반적인 의견은 재고할 필요가 있다."

라고 생각합니다. 이 말씀은 제가 경험하지 못한 부분을 경험하신 분의
소중한 충고로 잘 새겨 듣겠습니다. 다만, 제가 말씀드리고자 하는 바는
(원래 처음 글을 올린 의도는 성능 뿐 아니라 프로그램의 안정성도
재귀-비재귀 trade-off 의 기준으로 포함되어야 한다는 것이었습니다만)
재귀 호출이 갖는 생산성 측면에서의 우월성보다 때로는 프로그램의
안정성이나 치명적인 성능 저하를 막기 위해 비재귀로의 전환이 필수적인
부분도 있다는 것입니다. 이는 이미 위에서 말씀하셨듯이 님도 동의하시는
부분이라고 봅니다.

그리고, 제가 님의 의견에 계속 이의를 제기한 가장 큰 이유는, 님이 제가
말씀드린 비재귀로의 전환이 필수적인 부분에서조차 재귀를 유지하며 다른
방법으로 안정성을 확보하라고 주장하셨기 때문입니다. 물론, 그 다른
방법이 비재귀 변환보다 모든 점에서 더 나았다면 저 역시 그 방법을
배우는 것으로 논의가 종결되었겠지만, 결코 그렇다고 판단할 수 없기에
이야기가 길어졌습니다.

그리고, 마지막으로 아직까지는 앞서 그린(?) 그림에서 C 와 같은 경우에
비재귀로의 변환에 더 무게를 두고 싶습니다. 하지만, 앞으로 님께서
말씀하신 프로그램 개발의 생산성 같은 다른 요소에도 좀 더 무게를 두도록
하겠습니다.

그럼...

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.