dydsj0920   3년 전

내용 그대로 재귀함수로 구현할수 있는것들은 비재귀함수로 무조건 구현 가능한지
아니면 재귀 함수로만 구현 가능한 문제들이 있는지 궁금합니다.
제가 재귀함수가 많이 자신이 없습니다 프로그램의 흐름을 따라가는것도 힘든거 같구요ㅜㅜ

cheetose   3년 전

아예 불가능 하지는 않을 거 같지만 재귀함수를 비재귀함수로 바꾸는 거보다 재귀함수를 이해하는 게 더 쉬울 거 같아요

chogahui05   3년 전

좋은 질문인데.. 제가 허접해서 이 정도까지만 답변을 못 드릴 거 같아서 죄송합니다..

일단 함수 같은 경우.. (어셈블리 책을 보셨으면 아시겠지만)


call 하는 과정에서 스택에다가 쌓고 ret 하는 과정에서 스택에서 pop 시켜 버립니다.

함수가 리턴이 될 때, callee에서 caller로 돌아갈 수 있는 것도 호출을 할 때 복귀 주소를 따로 저장을 해 놓기 때문이죠. 어딘가에..

gets 같은 함수를 마구 마구 썼을 때 보안에 취약해 지는 이유도.

return address 값을 어떻게 어떻게 해서 자신이 원하는 값으로 덮어버릴 수 있거든요.. 예를 들어 0x48번지라던지.


하튼 함수 호출 자체가 스택과 비슷하게 동작(?) 같은 걸 하기 땜시..

재귀에서 비재귀로 바꾸는 거 역시 가능한 걸로 알고 있어요. 그게 '모든' 것이냐라고 물어보신다면 이야기가 달라질 거지만..

왠만해서는 가능한 걸로 알고 있고요.


밑은 그냥 제 주관적인 생각입니다.

사실. 코딩을 하시다 보면. 저도 뼈저리게 느끼고 있는 문제 중 하나이지만..

재귀냐 비재귀냐 보다는.. 빠르고 버그 없이 안정적으로 구현하는 게 꽤나 중요하더라고요.


https://www.acmicpc.net/proble...

당장 이 문제를 비재귀로 구현하려면 코드 줄 수부터 길어질 겁니다.. 이건 그나마 간단한 문제고요.


흔히들 많이 보시는 퀵 소트나 병합 정렬도

비재귀로 구현하려면 머리가 깨지실 겁니다. 저 또한 비재귀로 구현해 본 적이 없었습니다.


나중에 공부를 더 하시다 보면.

트라이라는 자료구조도 접하게 될 건데요. 이걸 또 비재귀로 구현하려면 머리가 많이 아파지지요.

세그멘트 트리도 마찬가지고요. 결국 재귀가 더 쉽고 편할 경우에는 재귀를 쓰시는 게..

yukariko   3년 전

모든 재귀는 비재귀식으로 변환할 수 있습니다.

그래서 재귀를 전혀 알 필요 없다는 사람도 많이 있구요. 이 부분은 지금도 논쟁이 치열한 것 같습니다.

제 생각엔 PS에서는 재귀가 필요한 것 같습니다. 재귀를 통하면 이해하기 쉽고 구현도 쉬워지는 경우가 자주 있기 때문이죠.

dydsj0920   3년 전

좋은 답변들 정말 감사드립니다. 공부 열심히 해야겠다는 생각만 드는군요! ㅋㅋ

댓글을 작성하려면 로그인해야 합니다.