Recursion Vs Iteration. -> Iteration win!

int what(int a) { if (a == 0) return a; else return what(a - 1); } int main() { what(10); }

....

"뭡니까 저건 -_-;?"

하는 질문이 나올 법한 이상한 코드입니다.

....

이건 어떄요?

int main() { int i; for (i = 0; i < 10; i++) }

....

같은 코드에요.

왠진 아시죠?-_-;

근데 제목이랑 관련이 있어 보이기도 하고 아니기도 하고...

속도도 별 차이 없어보이는데... 왜 붙여놨을까요?

if문의 비교 횟수는 물론, 반복 실행 횟수도 같습니다.









그.렇.지.만







Iteration이 압도적으로 빠릅니다.

지금이야 데이터가 훨씬 적지만, 대충 10만개만 되도 차이가 확연히 날 겁니다.

C언어 -> 어셈블러 -> 기계어코드로 변환되어 프로그램이 실행된다는건 다들 아시지요?

모르신다면 C언어 책 아무거나 맨 앞부분을 참조해주세요. 나와있어요 ㄱ-;

이 때 어셈블리어 수준에서 위의 두 코드가 어떻게 해석되는지 확인해 볼까요?

main :
  ....... '스택 초기화등 여러가지.
  push EAX
  jmp what
  pop EAX
  ..... ' 이하 생략
what :
  ...... '스택 초기화등 여러가지.
  pop EBX
  jne EAX, 0, what
  pop EAX
  push EAX
  INT 20h

이 부분이 재귀(Recursion)을 이용한 코드의 어셈블리형 파트입니다.

main :
  ..... ' 스택 초기화등 여러가지.
          mov EAX, 10
          mov ECX, EAX
loop :  sub ECX, 1
          jne ECX, 0, loop
  ..... ' 이하 생략

이 부분이 반복(Iteration)을 이용한 코드의 어셈블리형 파트이구요.

지금 뭐 MIPS나 IA-32등의 어셈블리 코드 구조가 모두 엉켜버린 상태라 좀 난잡할수도 있습니다만...

그런걸 무시해도 될 만큼 코드 길이에서 차이가 나고 있습니다.

함수 자체가 하나의 라벨이 되면서, (반복도 라벨을 붙였지만요.)

함수에 진입하기 전 push와 pop, 20h번 인터럽트를 발생시키는걸 볼 수 있습니다.(20h번 맞나... -_-;)

함수를 호출할 떄, 파라메터의 전달을 스택을 이용한 다는 부분에서 속도문제가 큼을 알 수 있습니다.

단순한 반복이라면 for문을 구성하는, 혹은 while이나 do-while을 구성하는 변수들을

모두 레지스터로 처리해버리면 훨씬 빠르겠지만, 함수로 호출해 재귀함수형으로 만들게 되면

함수 호출시마다 반복해서 함수에 따른 스택의 베이스포인터 처리, 스택에 대한 push, pop의 반복으로

좀 무지막지하게 느려질 수 있음을 알 수 있습니다.

스택은 메모리 영역에 잡히기 때문에, 레지스터보다 압도적으로 느린건 별 수 없는 사실이지요?