Tail Recursion과 최적화 이야기

By | 2009/10/01

  오늘 프로그래밍언어론 시간에 배운 개념으로 Tail Recursion이 있습니다. recursive call을 하는데 있어 call 후 return이 되어 돌아올 때 자신도 더 이상의 일을 하지 않고 바로 return하는 경우를 뜻합니다. 이렇게 되면 컴파일러가 최적화하기 쉽다는 얘기를 덧붙여 배웠습니다.

  그리고 교수님께서 값을 받아 1부터 그 값까지 더하는 함수인 sum을 만들었을 때 다음과 같은 코드는 tail recursion이 아니라고 말씀하셨습니다.

  1: int sum2(n)
  2: {
  3: 	if(1 == n)
  4: 		return 1;
  5: 	else
  6: 		return n + sum2(n-1);
  7: }

  왜냐하면 6번째 줄에서 sum(n-1)이 return되어 돌아오면 n과 더하는 연산을 하기 때문입니다.

  그러면서 저희에게 어떻게 하면 이를 tail recursion이 되도록 함수를 만들 수 있겠냐며 질문하셨습니다. 그래서 저는 지금까지 recursion을 무지하게 사용하였던 SICP를 공부할 때의 경험을 살려 답을 얘기하고 이를 칠판에 적었습니다.

  하지만 명확하지 못한 상태에서 얘기해서 교수님과 학우들이 받아들여지지 못한 듯싶었고, 방에 와서 이를 Scheme으로 짜보았습니다.

c15

  sum이라는 함수 안에 recursive한 함수를 하나 만들어서 그 안에서 tail recursion이되도록 하였습니다. 그리하여 값을 구해보니 문제 없이 값이 잘 나오고 있다는 것을 확인하였습니다.

(define (sum n)

 
(define (func k sum)

   
(if (= k 0)

       
sum

       
(func ( k 1) (+ sum k))

       
)

   
)

 
(func n 0)

 
)

(sum 10)

(sum 100)

(sum 1000)

 

  다음으로 이를 C 언어로 구현하여보았습니다.

c16

  1: #include <stdio.h>
  2: 
  3: int main(void)
  4: {
  5: 	printf("n is 10 : %d\n", sum(10));
  6: 	
  7: 	printf("n is 100 : %d\n", sum(100));
  8: 	
  9: 	printf("n is 1000 : %d\n", sum(1000));
 10: 	
 11: 	return 0;	
 12: }
 13: 
 14: // Sum function from 1 to n
 15: int sum(int n)
 16: {
 17: 	return func(n, 0);
 18: }
 19: 
 20: // tail recursion
 21: int func(int k, int sum)
 22: {
 23: 	if(0 == k)
 24: 		return sum;
 25: 	else
 26: 		return func(--k, sum+k);
 27: }

  역시 제대로 돌아가는 것을 확인하였습니다.

  그럼 컴파일러가 어떤 어셈블리 코드를 내놓는지 확인하였습니다. 작동 환경은 Fedora 11 32bit Intel CPU / gcc 4.4.1입니다.

  어셈블리 코드를 읽어보니 딱히 최적화라고 볼만한 것이 보이지 않았습니다. 그저 코드 하나하나를 어셈블리로 구현한 정도에 그쳤습니다. 그래서 O2 옵션을 주어서 살펴보았습니다.

c18

  놀랍게도 sum 함수가 recusion하는 함수를 부르는 것을 파악하여 iterative하게 구현하였습니다. 그리하여 func 함수를 호출하지 않아도 문제를 풀 수 있습니다. func 함수 역시 sum 함수와 마찬가지로 구현되어 있습니다.

  그럼 이것이 tail recursion이라는 것을 알고 행한 최적화일까요? 그래서 위의 sum2 함수를 –O2 옵션으로 한 어셈블리어를 보았습니다.

c20

  제가 어셈블리어를 읽는 실력이 낮아 이렇게 간단히 주석을 달았습니다. 보시면 아시겠지만 여기서도 recusive를 하지 않고 iterative로 바꾸었습니다. 하지만 위에 나오는 코드보다는 조금 더 복잡하더군요.

 

  sum 함수의 tail recursion 모양 만들기부터 시작하여 gcc 최적화 결과까지 확인하였습니다. 요즘 컴파일러가 엄청 똑똑하다더니 정말 대단하네요. 사람이 개떡같이 코드를 짜도 찰떡같이 좋은 코드를 내놓습니다.^^ 하지만 사람이 조금이라도 잘 짠다면 거기에 부응(?)하여 더욱 좋은 코드를 내놓는다는 것을 알았습니다.

  시험 공부 및 프로젝트 해야 하는데 뻘글을 쓰고 있었습니다.OTL..

 

참조

4 thoughts on “Tail Recursion과 최적화 이야기

  1. nvec

    수업 내용을 이렇게 일일히 검토하시다니 정말 대단하네요.
    전 대체로 머리로 이해가 완료되면 그냥 넘기거든요
    정말 이해가 안될때만 해보고요.
    nosyu님이 저희과 에이스라는 소문이 그냥 나온게 아닌가 봐요 ㅎ

    Reply
    1. NoSyu

      제가 에이스라는 소문은 소문에 불과하다는 사실…OTL…..

      이번 것은 약간 오기가 생겼다고 할까요?
      이렇게 하면 되겠는데~ 라고 하였으나 명확하게 하지 못해서 이를 완수하고자 직접 만들어보고 이왕 하는 것 최적화도 알아보자는 생각에 하였습니다.
      글을 적는 이유는 훗날 같은 삽질을 하지 않게 만들기 위함입니다.^^;;
      워낙 기억력이 안 좋아서..OTL…

      Reply
  2. 근영

    “다른 사람이 인정해 줄때 비로소 성장했다는걸 느낀다”
    라는 말이 갑자기 생각났음 -ㅁ-

    Reply
    1. NoSyu

      호오… 그런 말이 있군.
      다른 사람이 인정해 준다라…
      그런 일은 흔하지 않아서…OTL….
      다만, 나를 뒤돌아보면 가끔 성장하였다는 것을 느끼고 있어.
      이 블로그도 그 뒤돌아보게 만드는 것 중에 하나이고…^^

      Reply

Leave a Reply