프로그래밍을 처음 접하시는 분이라면, 재귀함수를 지금 이해하는것이 다소 부담스러울 수 있으므로 내용이 많이 부담스럽다면 다음 기회에 공부하시는것을 추천드립니다.

재귀함수란 함수내에서 자기 자신을 다시 호출하는 형태의 함수입니다.

기본적인 형식

void recursive() {
	printf("반복호출\n");
	recursive(); // 자기 자신을 호출
	return;
}

위의 함수에서 보면 함수가 호출되면 "반복호출" 이라는 출력을 한 후
3행에서 다시 함수를 호출하여 "반복호출"을 출력하고 또 3행에서 다시 함수를 호출하여...
무한이 반복되는 것을 보실 수 있습니다.
그렇다면 완료되지 않은 함수를 다시 호출하는 것이 가능한 것인가?
그렇다. recursive 함수를 실행하는 중간에 다시 recursive 함수를 호출하면, recursive 함수의 복사본을 하나더 만들어 복사본을 실행하게 됩니다.
위의 코드는 재귀함수에는 재귀의 탈출 조건이 없는것이 문제 입니다.

재귀의 탈출 조건

재귀함수는 재귀를 탈출할 수 있는 조건이 반듯이 있어야 합니다.

#include <stdio.h>

void recursive(int);

int main(void) {
    recursive(3);
    return 0;
}

void recursive(int count) {
    if (count == 0) { // 재귀함수의 탈출 조건
        return;
    }
    printf("recusive call : %d\n", count);
    recursive(count-1); // 다시 호출할때 1을 빼서 점차적으로 탈출조건 맞도록 함
    return;
}

11행에서 recursive함수의 탈출조건을 만들었습니다.
먼저 3행에서 recursive​함수를 호출하면서 인자값으로 3을 전달 하였습니다.
재귀함수의 흐름은 다음과 같습니다

1. recursive​(3) 이며 11행의 조건이 만족되지 않으며 14행으로 이동 15행에서 recursive​(2)를 호출하게 됩니다.
2. recursive​(2) 이며 11행의 조건이 만족되지 않으며 14행으로 이동 15행에서 recursive​(1)를 호출하게 됩니다.
3. recursive​(1) 이며 11행의 조건이 만족되지 않으며 14행으로 이동 15행에서 recursive​(0)를 호출하게 됩니다.
4. recursive​(0) 이며 11행의 조건을 만족하여 return종료 하게 됩니다.
5. 3번의 recursive(1)함수의 16행이 실행되며 return 종료하게 됩니다.
6. 2번의 recursive(2)함수의 16행이 실행되며 return 종료하게 됩니다.
7. 1번의 recursive(3)함수의 16행이 실행되며 return 종료하게 됩니다.

재귀함수는 일반적으로 자료구조나, 알고리즘의 어려운 문제를 단순화 하는데 사용됩니다.

팩토리얼 디자인 사례

정수 n 의 팩토리얼은 n!로 표시하며 수식은 다음과 같다.
n! = n × (n-1) ×​ (n-2) ×​ (n-3) ×​ . . . ×​ 2 ×​ 1
따라서
5! 은 5 ×​4 ×​3 ×​2 ×​1 이고,
4! 은 4 ×​ 3 ×​ 2 ×​ 1 ​입니다.
그래서
n! 은 n ×​(n-1)! 이라고 볼 수 있습니다.
그리고 n이 1이상인 경우의 수식을 n ×​f(n-1)로 표현 할수 있고 다음과 같은 코드로 나타낼 수 있습니다.

if(n >= 1) {
    return n * factoral(n - 1);
}

그리고 n이 0일때 결과값 1은 다음과 같이 표현됩니다.

if(n == 1) {
	return 1
}

다음은 팩토리얼 함수를 호출하는 예제입니다

#include <stdio.h>

int factorial(int);

int main(void) {
	printf("1! = %d\n", factorial(1));
	printf("3! = %d\n", factorial(3));
	printf("5! = %d\n", factorial(5));
	printf("9! = %d\n", factorial(9));
	return 0;
}

int factorial(int n) {
	if (n == 0) { // 재귀함수의 탈출 조건
		return 1;
	}
	else {
		return n * factorial(n - 1);
	}
}

연습문제

사용자로부터 1개의 정수를 받고 2의 n승을 구하는 함수를 재귀적으로 구현해보자.

소스보기