[자료구조] 재귀 함수, 예시, 작성 요령

재귀

함수가 자기 자신을 호출하는 것을 통해 답을 구하는 방식이다. 피보나치, 하노이의 탑 등 점화식 문제와 관련이 깊다. 간단한(?) 식을 통해 멀리 있는 항의 값을 구하는 종류의 문제에 유도용하고, 이진탐색, DFS 등 여러 알고리즘에 사용된다. 잘 사용하면 매우 효율적으로 작동하고 코드도 깔끔해지지만, 잘못 사용하면 불필요한 반복호출이 일어나는 등(ex. 피보나치) 반드시 필요한 곳에서만 사용하는 것이 좋다. 

(개인적인 의견: 사실 잘 사용했을 때 코드가 깔끔해진다는 것도 글자 수가 줄어든다 정도지, 코드를 읽고 해석하는 게 편해진다는 얘기는 아닌 것 같다. 오히려 글자 수, 줄 수가 많아지더라도 웬만한 경우엔 반복문을 사용하는 게 심적으로도 유지보수적으로도 더 편할 것 같다. 재귀로 작성할 수 있는 코드는 추가 변수들을 몇 개 두면 충분히 반복문으로도 작성할 수 있다.)

재귀 함수의 형태

1. 재귀함수는 재귀 호출을 멈춰줄 베이스 케이스가 필요하다.

2. 재귀함수는 자기 자신을 파라미터를 바꿔서 호출하는 재귀 부분이 있어야 한다(재귀 케이스 필요). 이때 파라미터는 베이스 케이스에 가까워지는 방향으로 넣어지도록 해야 한다.

예시 및 재귀함수 작성 요령

1. 1부터 k까지 더하는 재귀함수

int sum(int k) {
	if (k == 1) return 1;
	return k + sum(k - 1);
}

2. 입력받은 정수의 각 자릿수를 한 줄씩 순서대로 출력하는 함수

void print_digits(int n) {
	if (n < 10) {
    	printf("%d", n);
    } else {
    	print_digits(n / 10); // 일의 자리를 없앰.
        printf("%d", n % 10); // 일의 자리 출력.
        // 높은 자리부터 낮은 자리 순서대로 출력해야 하므로, 
        // 매개변수에 높은 자리를 포함하고 있는 재귀 호출을 먼저 하고 나서 일의 자리를 출력한다.
    }
}

3. 입력받은 정수의 각 자릿수를 한 줄씩 반대로 출력하는 함수

void print_digits_reversely(int n) {
	if (n < 10) {
    	printf("%d", n);
    } else {
        printf("%d", n % 10); // 일의 자리 출력.
    	print_digits(n / 10); // 일의 자리를 없앰.
        // 낮은 자리부터 높은 자리 순서대로 출력해야 하므로, 
        // 일의 자리를 먼저 출력하고 나서 재귀 호출을 한다.
    }
}

4. 하노이의 탑 (작성 중)

void hanoi(int n) {
	
}