제가 게임을 만들면서 지금 고민인게
비주얼드처럼 2차원 배열에서 한 유닛 주위에 자기와 같은 유닛이 있으면 그 붙어있는 정도를 세는 프로그램을 만들어야 합니다.
저는 이것을 오른손 법칙에 의해 (우선 오른쪽을 고려하는 알고리즘) 이 프로그램을 구현하려고 하는데
두가지 방법이 있어 어느것이 더 성능상 좋을지 고민입니다.
하나는 재귀를 써서 푸는 방법이 있고
다른 하나는 반복문을 써서 푸는 방법이 있는데
재귀의 경우 우선 직관적으로 이해하기 쉽고
반복문의 경우 조건문이 좀 들어가야 합니다.
그런데 어디서 듣기로 재귀는 좋지 않다는 말이 있어 이렇게 질문을 올립니다.
어느 방법을 써야 더 성능상 좋고 더 좋은 코드가 될까요?
질문하신 분이 말하는 재귀(recursion)는 메소드 안에서 다시 그 메소드를 호출하는 걸 말하시는 것 같네요.
메소드를 호출하는 비용은 생각보다 크기때문에 반복으로 똑같이 구현할 수 있으면 반복(iteration)이 좋습니다.
참고: 피보나치 함수를 재귀와 반복으로 구현(http://www.ics.uci.edu/~eppstein/161/960109.html)한 예제입니다.
재귀는 조건 잘못주면 stack overflow가 날수도 있구요... (힙과 달리 stack은 크기가 크지 않습니다.)
원래 함수콜 혹은 메소드 콜은 모두 스택에 쌓는 형태입니다. return할때 빼는거죠....
function call은 원래 오버헤드가 꽤나 큽니다. 물론 if 문 자체가 많이 들어가는것도 오버헤드가 있습니다만...
실제 같은 문제를 놓고 시뮬레이션 몇번 하신 담에 고르셔도 될겁니다.
(언젠가 들은 얘긴데 일부 컴파일러에서는 최적화할때 재귀의 종류에 따라서 재귀를 반복문 형태로 바꾸기도 한다고 합니다.)
똑같다면 if문이 하나라도 적은쪽이 빠르지 않을까요?
while이 재귀문이고 for문이 반복문을 뜻하는 것일까요?
음.. 어렵네요....
1만번짜리 100만번짜리 처럼 엄청나게 많은게 아니면 비쥬얼드정도라면,
while로 하나 for로 하나 속도차이를 느끼시지는 못할것 같아요
while문이나 for문에서 속도차이를 줄이려고 하실 때
그래픽 출력쪽에서 과부하를 조금이라도 줄이시는게 성능향상에 도움이 될 것 같아요(게임이라고 전재했을 때)