반복문(for 문)과 재귀함수의 속도 비교 - [C#]

개발 노트/C#  2013.03.14 09:00

안녕하세요. 명월입니다.
이번 포스트에서는 반복문과 재귀함수의 속도 차를 조사해 보겠습니다.


사실 오래전에 포스트를 했었는데 조금 잘못된 정보가 많이 포함되어 있어서 현재 정확한 코드를 다시 작성하였습니다.



먼저 첫 번째는 재귀함수를 실행해서 시간이 얼마나 나오는지 밀리초로 체크하고 두 번째는 반복문을 실행해서 시간이 얼마나 나오는지 체크합니다.
IO의 영향을 최대한 빼기 위해 시간 측정이 끝나면 Console.Write로 출력하겠습니다.



재귀 함수의 경우는 stack 메모리에 현재 상태를 누적시키기 때문에 깊이가 깊어질 수록(dept) 느려질 수밖에 없고 for 문은 초깃값이 변수형태이지만 실제 계산은 레지스터에서 일어나기 때문에 반복문에 대한 속도제약은 없습니다.
반복문과 재귀함수의 결괏값도 10배의 넘는 속도 차가 발생하네요.


그러면 사용도 복잡하고 느린 재귀함수를 굳이 사용하겠나 싶겠지만 반대로 탐색의 알고리즘은 반복문으로 작성할 경우 복잡도가 많이 올라갑니다. 그럴 경우는 재귀함수를 사용할 수밖에 없습니다.
C#으로 작성된 것은 아니지만, 지하철 탐색 소스를 확인해 보시면 재귀 함수의 활용도를 확인할 수 있겠네요.


링크 - [Java / 자바] 알고리즘 - 지하철 노드 탐색 (연결리스트, 트리 탐색 응용)


이전 잘못된 정보게재를 지적해 주신 희나람님과 sunyzero님께 감사합니다.
링크 - 희나람님 블로그
링크 - sunyzero님 블로그


댓글 13개가 달렸습니다.
댓글쓰기
  1. Hansik's Drink
    2013.03.14 10:46 신고 |  수정/삭제  댓글쓰기

    다녀간답니다 ~ ^^
    좋은 하루를 보내세요~

  2. ATJJYLOG
    2013.03.14 17:49 신고 |  수정/삭제  댓글쓰기

    이렇게 유용한 블로그가 있는줄 몰랐네요. 앞으로 자주와서 공부할게요 ^^ 좋은 포스팅 감사드립니다.

  3. 심규현
    2013.03.19 20:52 신고 |  수정/삭제  댓글쓰기

    안녕하세요 지금 C# 프로그램을 하나 만들고 있는데요

    이것저것 여쭤보고 싶은게 있는데

    혹시 가능하시다면

    cools2hyun@nate.com

    제 네이트온 아이디인데 대화가능할까요 ...ㅠㅠ

  4. 희나람
    2013.03.27 23:37 신고 |  수정/삭제  댓글쓰기

    저도 이상하게 생각했는데, 소스를 보니,
    tostring 하는 과정에서 느려질 수 밖에 없겠네요.

    윗분이 더 세심하게 달아두셨네용..

    • 明月 v명월v
      2013.03.28 23:55 신고 |  수정/삭제

      먼저 블로그 방문 감사합니다.
      먼저 좋은 지적 감사하구요.. 주말에 I/o 가 아닌 것으로 테스트를 해볼께요..^^;

  5. sunyzero
    2013.03.28 00:13 신고 |  수정/삭제  댓글쓰기

    결과가 좀 이상합니다.
    일반적으로 재귀함수는 스택 프레임 할당구조 때문에 느릴 수 밖에 없습니다.

    제 생각에는 콘솔 출력하는 부분의 I/O latency 때문에 부정확한 결과가 나왔다고 생각됩니다.
    (일반적으로 I/O latency를 포함하는 코드의 성능 측정는 무의미한 코드가 됩니다.)

    매번 콘솔 출력하는 부분을 마지막에 한번 출력하는 것으로 바꾸시고 해보면 아마도 for문이 더 빠를겁니다.

    (수정을 했더니 희나람님 글이 위로 올라갔네요.)

    • 明月 v명월v
      2013.03.29 00:01 신고 |  수정/삭제

      안녕하세요... 블로그 방문 감사합니다.
      좋은 지적 감사하구요... 주말에 I/O 가 아닌 값으로 다시한번 측정을 해보겠습니다.
      저는 개인적으로 Stack 이 빠르다는 입장이거든요..
      왜냐면 재귀는 mov mov 지만 for문은 mov , add, mov, add 라 생각해서 입니다.
      그러나 데이터가 많아 지면 for문이 빠를꺼라 생각하여 했는데. 저도 의외였거든요...


  6. 2013.06.05 02:36 |  수정/삭제  댓글쓰기

    비밀댓글입니다

  7. 김영수
    2013.11.14 13:47 신고 |  수정/삭제  댓글쓰기

    재귀함수편하긴한데
    오버플로우.. 매번뜨던데