Copyright (c) 2015-, All Rights Reserved by Kwanghoon Choi
(아래 강의 노트를 자유롭게 이용하되 다른 웹 사이트 등을 통한 배포를 금합니다.)

The C Programming Language 2nd Ed. by Kerninghan & Ritchie ( Ch.4, reverse )

문자열을 뒤집는 reverse 함수를 재귀함수로 작성해보자. 단, 이 함수의 인자로 주어진 문자열 s가 차지하는 공간 만을 사용하되 별도의 배열을 사용하지 않는다. ("in place" 버전의 reverse 함수를 작성)

함수 원형
  void reverse(char s[]);

reverse 함수 사용 예:
  char str[100];
  strcpy(str, "Yonsei University");

  printf("[%s] => ", str);
  reverse(str);
  printf("[%s] \n", str);

실행 결과:
  [Yonsei University] => [ytisrevinU iesnoY] 

기본적인 아이디어는 함수 reverse는 길이가 0인 빈 문자열 ""에 적용하거나 길이가 1인 문자열에 적용하면 그 결과는 인자로 주어진 문자열과 동일하다. 길이가 2이상인 문자열에 적용하면 이 함수의 인자로 주어진 문자열을 첫번째 문자 c와 그 이후의 문자열 therest로 분리할 수 있다. therest 문자열(s의 두번째 문자부터 그 이후의 문자열)을 reverse 함수를 재귀호출해서 뒤집은 다음, 그 결과 문자열을 왼쪽으로 한 칸씩 이동시킨다. 마지막으로 원래 첫번째 문자 c를 문자열의 맨 마지막 위치로 이동시킨다.

이 아이디어를 사용한 코드는 다음과 같다.

void reverse(char s[]) {
 int i;
 int len = strlen(s);

 if (len == 0) return;
 else if (len == 1) return;
 else { // len > 1
     char s0 = s[0];
     reverse(&s[1]);

     // shift s[1]~s[len-1] to s[0]~s[len-2]
     for(i=1; i<len; i++) {
       s[i-1] = s[i];
     }

     // copy s0 to s[len-1]
     s[len-1] = s0;
  }
}

아래의 main 함수를 사용해서 재귀함수 reverse를 테스트해보자.

#include <stdio.h>
#include <string.h>
#define MAX_LEN 100
void reverse(char s[]);

char tests[][MAX_LEN] = {
 "abc",
 "",
 "Republic of Korea",
 "Yonsei University"
};

int main() {
 char str[MAX_LEN];
 int i;

 for(i=0; i<sizeof(tests)/MAX_LEN; i++) {
    strcpy(str, tests[i]);

    printf("[%s] => ", str);
    reverse(str);
    printf("[%s] \n", str);
 }

 return 0;
}

[끝]