2. 재귀 (충남대 알고리즘 강의록)

충남대학교 컴퓨터공학과 이영석 교수님의 "알고리즘" 강의 실습 내용입니다.

• 실습 문제들의 코드 위주로 구성되어 있습니다.

문제 1: 피보나치 수열 구하기 §

#include <iostream>
 
using namespace std;
 
/**
 * 피보나치 수열을 재귀적으로 구하기 위한 함수
 */
int pib(int nInput) {
	if(nInput == 0) { // 0번째 값에 대한 종료조건
		return 0;
	} else if(nInput < 3) { // 1번째, 2번째 값에 대한 종료조건
		return 1;
	} else {
		return pib(nInput - 1) + pib(nInput - 2); // n - 1, n - 2번째에 대한 결과를 재귀적으로 구하여 더함
	}
}
 
int main() {
	int nInput;
	cin >> nInput;
	cout << pib(nInput) << endl;
}

문제 2: 유클리드 호제법을 이용한 최대공약수 구하기 §

#include <iostream>
 
using namespace std;
 
/**
 * 유클리드 호제법을 이용해 최대공약수를 재귀적으로 구하기 위한 함수
 */
int solve(int nI, int nJ) {
	int nRemain = nI % nJ;
	if(nRemain == 0) { // 나머지가 0일 경우에 제수를 반환
		return nJ;
	} else {
		return solve(nJ, nRemain); // 그렇지 않은 경우에 제수와 나머지를 재귀적으로 호제법을 적용함
	}
}
 
int main() {
	int nI, nJ;
	cin >> nI >> nJ;
	cout << solve(nI, nJ) << endl;
}

문제 3: 피라미드의 무게 구하기 §

#include <iostream>
#include <vector>
 
using namespace std;
 
long unsigned int nEnd; // 피라미드의 층수를 저장할 global 변수
 
/**
 * 벡터의 원소 합을 구하는 함수
 */
long unsigned int sum(vector<long unsigned int> vecInput) {
	long unsigned int nRes = 0;
	for(long unsigned int i = 0; i < vecInput.size(); i++) {
		nRes += vecInput[i]; // 벡터에서 값을 하나씩 꺼내 축적해줌
	}
	return nRes;
}
 
/**
 * 피라미드의 무게를 재귀적으로 구하기 위한 함수
 */
long unsigned int pyramid(vector<long unsigned int> vecInput, long unsigned int nAcc, long unsigned int nPhase) {
	if(nPhase == nEnd) { // 주어진 층수에 도달하면 지금까지 구한 무게를 반환
		return nAcc;
	} else {
		vector<long unsigned int> vecNext; // 현재 층의 원소들을 저장할 벡터
		vecNext.push_back(1); // 벡터에 1을 넣어줌
		for(long unsigned int i = 0; i < vecInput.size() - 1; i++) {
			vecNext.push_back(vecInput[i] + vecInput[i + 1]); // 해당 원소 바로 윗층에 있는 두 원소의 값을 더하여 현재 층의 원소 값을 구해냄
		}
		vecNext.push_back(1); // 벡터에 1을 넣어서 현재 층을 마무리함
		// 현재 층을 다음 층으로 전달하고 현재 층의 무게를 지금까지 구한 무게에 더해주며 층을 한단계 올려줌
		return pyramid(vecNext, nAcc + sum(vecNext), nPhase + 1);
	}
}
 
int main() {
	cin >> nEnd;
	vector<long unsigned int> vecInit;
	vecInit.push_back(1); // 피라미드의 맨 꼭대기에는 1밖에 없으므로 1을 넣어준 뒤
	cout << pyramid(vecInit, 1, 1) << endl; // 다음 층부터 연산하도록 지시
	return 0;
}

문제 4: 계단오르기 §

#include <iostream>
 
using namespace std;
 
/**
 * 계단의 갯수인 nN과 한번에 올라갈 수 있는 양인 nM을 인자로 줘 경우의 수를 세도록 함
 */
int solve(int nN, int nM) {
	if(nM <= 1) {
		return 1; // 계단의 갯수가 1보다 같거나 작으면 한번에 올라 갈 수 있음
	} else if(nM > nN) {
		return solve(nN, nN); // 한번에 올라갈 수 있는 계단의 최대가 계단의 수보다 크면 최대 계단의 수만큼 올라갈 수 있는것이나 마찬가지
	} else {
		int nRes = 0; // 한번에 올라갈 수 있는 계단의 수가 1일때부터 순차적으로 계산해 그 결과를 축적하기 위한 변수
		for(int i = 1; i <= nM; i++) {
			// 1 <= i <= nM인 i에 대해 먼저 i개의 계단을 올라간 뒤 남은 계단만큼을 한번에 최대 nM개 올라갈 수 있는 상태로 경우의 수를 재귀적으로 구함
			// i개의 계단을 먼저 올라가면 남은 계단은 nN - i개 일 것이고 한번에 올라갈 수 있는 계단의 최대 갯수는 여전히 nM이므로 이때의 경우의 수를 구함
			nRes += solve(nN - i, nM);
		}
		return nRes;
	}
}
 
int main() {
	int nN, nM;
	cin >> nN >> nM;
	cout << solve(nN, nM) << endl;
}