67 함수에서 재귀호출 사용하기
함수 안에서 함수 자기자신을 호출하는 방식을 재귀호출(recursive call)이라고 합니다. 재귀호출은 일반적인 상황에서는 잘 사용하지 않지만 알고리즘을 구현할 때 매우 유용합니다. 보통 알고리즘에 따라서 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많습니다.
이번에는 재귀호출을 사용하는 방법과 주의점을 알아보겠습니다. 참고로 재귀호출은 코드가 간단한 편이지만 머릿속으로 생각을 많이 해야됩니다. 그래서 초보자들은 한 번에 이해가 되지 않을 수 있습니다.
67.1 재귀호출 사용하기
먼저 간단한 재귀호출 함수를 만들어보겠습니다. 다음 내용을 소스 코드 편집 창에 입력한 뒤 실행해보세요.
recursive_function_error.c
#include <stdio.h> void hello() { printf("Hello, world!\n"); hello(); // hello 함수 안에서 hello 함수 호출 } int main() { hello(); // hello 함수 최초 호출 return 0; }
실행 결과
Hello, world! Hello, world! Hello, world! ...(생략)
hello 함수 안에서 다시 hello 함수를 호출하고 있습니다. 소스 코드를 컴파일하여 실행해보면 "Hello, world!" 문자열이 계속 출력되다가 프로그램이 종료됩니다. 왜냐하면 hello 함수가 자기자신을 계속 호출하다가 스택이 넘쳐서 스택 오버플로우(stack overflow) 에러가 발생하기 때문입니다(함수 호출은 메모리의 스택을 사용합니다).
재귀호출을 사용하려면 반드시 다음과 같이 종료 조건을 만들어주어야 합니다.
recursive_function_exit_condition.c
#include <stdio.h> void hello(int count) { if (count == 0) // 종료 조건을 만듦. count가 0이면 다시 hello 함수를 호출하지 않고 끝냄 return; printf("Hello, world! %d\n", count); hello(--count); // count를 감소시켜서 다시 hello에 넣음 } int main() { hello(5); // hello 함수 호출 return 0; }
실행 결과
Hello, world! 5 Hello, world! 4 Hello, world! 3 Hello, world! 2 Hello, world! 1
먼저 hello 함수의 반복 횟수를 계산하기 위해 매개변수 count를 지정합니다. 그리고 count가 0이라면 hello 함수를 호출하지 않고 끝냅니다. 만약 0이 아니라면 "Hello, world!"를 출력하고 count의 값을 1씩 감소시켜서 hello 함수를 호출할 때 넣어줍니다.
void hello(int count) { if (count == 0) // 종료 조건을 만듦. count가 0이면 다시 hello 함수를 호출하지 않고 끝냄 return; printf("Hello, world! %d\n", count); hello(--count); // count를 감소시켜서 다시 hello에 넣음 }
main 함수에서는 hello 함수를 반복할 횟수를 넣어서 호출해줍니다. 이렇게 하면 hello 함수가 재귀호출을 할 때마다 count에 들어있는 값이 1씩 감소하고, 0이 되면 재귀호출을 끝냅니다.
hello(5); // hello 함수 호출
