재귀 함수 C++

개요

함수란 무엇인가? 코드를 기능 단위로 묶어둔 것이다.

return type funcname() {
	body
}

와 같은 형식을 가진다. 지역/전역/함수를 사용할때 어떤 메모리 영역에서 쓰이는지 잘 구분해야 한다.

 

재귀는 다시 돌아오다 라는 뜻으로 재귀 함수는 다시 돌아오는 함수이다. 즉 다시 실행되는 함수 (run / recall)

재귀 함수는 자기 자신을 리턴 혹은 호출 하므로 종료 조건을 설정하지 않으면 원하는 의도가 나오지 않을 가능성이 매우 높다. (함수를 호출하는 것 자체가 메모리를 사용하는 것이므로 while처럼 무한루프에 빠지진 않을 것이다.)

따라서 재귀 함수를 사용할 당시엔 종료 조건을 설정해 주어야 한다.

 

예제

1. 무한 루프

코드

#include <iostream>

using namespace std;

void hello() {
	cout << "Hello\n";
	return hello();
}

int main() {
	hello();
}

이 코드는 무한 루프에 빠지게 된다.

 

2. 종료 조건 설정

코드

#include <iostream>

using namespace std;

void hello(int n) {
	if (n >= 10) return;
	cout << "Hello\n";
	return hello(n + 1);
}

int main() {
	hello(0);
}

이 코드는 종료 조건을 설정하여 매개변수로 받은 n값이 10이 될 경우 재귀를 빠져나오게 된다.

 

출력

Hello
Hello
Hello
Hello
Hello
Hello
Hello
Hello
Hello
Hello

 

3. 함수의 종료 시점

재귀 함수는 설정해 놓은 조건에 도달하여 return되게 되면 뻗었던 경로에서 다시 돌아오게 된다.

즉 재귀 호출 앞과 뒤의 실행되는 시점이 다르다.

 

코드

#include <iostream>

using namespace std;

void hello(int n) {
	if (n >= 5) {
		return;
	}
	cout << n << " "; // 재귀 호출 전 실행
	hello(n + 1);
	cout << n << " "; // 재귀 호출 후 실행
}

int main() {
	hello(0);
}

 

출력

0 1 2 3 4 4 3 2 1 0

 

4. 재귀의 기본 구조

1. 재귀에 대한 대략적인 그림 그리기
2. 재귀의 반복 범위 설정하기
3. 기저 조건(종료 조건) 설정하기
4. 재귀 이전 실행 코드 및 재귀 이후 실행 코드 작성하기

 

실습

1. 주사위 문제

N개의 주사위가 주어졌을때 나올 수 있는 모든 경우의 수를 구하기

 

코드

#include <iostream>

using namespace std;

int n = 3;
int DAT[10];

void dice(int now) {
	if (now >= n) {
		for (int i = 0; i < n; i++) {
			cout << DAT[i] << " ";
		}
		cout << "\n";
		return;
	}
	for (int i = 1; i < 7; i++) {
		DAT[now] = i;
		dice(now + 1);
		DAT[now] = 0;
	}
}

int main() {
	dice(0);
}

 

출력

1 1 1
1 1 2
1 1 3
...
6 6 4
6 6 5
6 6 6