[알고리즘/백준] 재귀함수

재귀함수는 자기 자신을 다시 불러오는 함수이다.

기본적인 형태는 다음과 같다.(기능적 구현은 전부 제외했다)

void function(int num){
	if(num==1){
    	cout<<"마지막 출력"<<endl;
        return;
    }
    function(num-1);
}

function()이라는 함수 안에 다시 function()을 호출하게 된다.

여기서 중요한 포인트는 매개변수이다.

자신을 다시 호출하는 부분의 매개변수에 똑같은 num을 주는 것이 아닌, num-1을 주는 것.

(똑같은 num을 주게 되면 무한루프에 빠지게 되는 것을 유의하라.)

num-1을 매개변수로 주게 되면, 부르는 함수의 횟수가 점점 감소하게 된다.

이때, function안에 자신이 멈추고자 희망하는 수를 if문 안에 넣어 호출을 종료하면 끝이 난다.

 

요약하자면 다음과 같다.

• function()안에 function() 적기
• 재호출된 function()의 매개변수를 초기의 function()보다 감소하여 넣기
• 초기의 function()안에 호출을 종료하는 if조건문 넣기

---

기능적 구현의 형태는 다음과 같다.

백준 '17478번 재귀함수가 뭔가요?'을 푼 예시이다.

#include<iostream>
#include<string>
using namespace std;

void bar(int num) {
	for (int i = 0; i < num; i++) {
		cout << "____";
	}
}

void first(int num) {
	string arr[4];
	arr[0] = "\"재귀함수가 뭔가요?\"";
	arr[1] = "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.";
	arr[2] = "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.";
	arr[3] = "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"";
	
	for (int i = 0; i < 4; i++) {
		bar(num);
		cout << arr[i] << endl;
	}
}

void function(int num,int key) {
	if (num == 0) {
		bar(key);
		cout << "\"재귀함수가 뭔가요?\"" << endl;
		bar(key);
		cout << "\"재귀함수는 자기 자신을 호출하는 함수라네\""<<endl;
		bar(key);
		cout << "라고 답변하였지." << endl;
		return;
	}
	else {
		first(key);
		function(num - 1,key+1);
	}
	bar(key);
	cout << "라고 답변하였지." << endl;
}

int main() {
	int num;
	cin >> num;

	cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다."<<endl;
	function(num,0);
}

해당 예시처럼 하나 이상의 매개변수를 넣어 자신이 희망하는 구조에 맞는 형태로 활용할 수 있다.

 

⛏️ 깃헙 해당 코드 주소

: 코드를 더 가독성 있게 볼 수 있으며, 다른 백준 문제의 풀이 역시 참고할 수 있다.