C++ 재귀함수

재귀 함수는 굉장히 어렵지만, 이해를 한다면 어떤 문제를 쉽게 해결 할 수 있는 방법을 제공한다.

------------------------------------------------------------------------------------------------

생각해야 할 점 

1 부터 10까지 자연수 중 세 개의 숫자를 활용하여 10을 만들어라

>> 쉽게 반복문으로 구할수 있다. 

>> 반복문 3번 사용하면 된다. 

1 부터 10까지 자연수 중 n 개의 숫자를 활용하여 50을 만들어라

> n 중 반복문을 사용해서 구하기는 미친 짓이다.

------------------------------------------------------------------------------------------------

Binary 를 생각해 보자 

단!! 재귀함수시 가장 중요한것은 

1. 매개변수 설정 

> 무엇을 들고 있을지 ( ex) getBinary( int num ) >> num 이 매개 변수가 된다. 

2. 탈출구 설정

> 탈출구는 반드시 매개변수와 상관관계가 있어야 한다. 

3. 로직 구현

2진수 출력

void getBinary(int num)

{

if(num == 1 )

cout<< '1';

else if( num == 0)

cout<< '0';

else

{

getBinary(num/2);

cout<< num % 2;

}

}

재귀 함수는 절대로 왔다 갔다 하는 문제로 생각하면 어렵다.

Binary(10){

if(10 ==1){

}

Binary(5){

if(5 ==1){

}

Binary(2)

printf(5%2);

}

printf( 10% 2 );

}

밑에서 하나씩 열린다고 생각하면 좀 쉽다.

------------------------------------------------------------------------------------------------

입력

첫 번째 줄에 숫자를 입력 받는다. 숫자의 크기는 20보다 작은 자연수이다.

예제 입력

3

예제 출력

1213121

mountain

void getMon(int num)

{

if(num == 1)

cout<<'1';

else{

getMon(num-1);

cout<<num;

getMon(num-1);

}

}

int main()

{

int num;

cin >>num;

getMon(num);

return 0;

}

재귀문제는 트리구조로 생각하면 쉽다.

마운틴 문제는 위치를 바꾸는 것에 따라서 

중위, 후위, 전위 로 바뀐다.

-----중위

getMon(num-1)

printf(num)

getMon(num-1)

-----전위

printf(num)

getMon(num-1)

getMon(num-1)

-----후위

getMon(num-1)

getMon(num-1)

printf(num)

------------------------------------------------------------------------------------------------

Tobin 문제 

예제 입력

2 1

예제 출력

10
01

 

예제 입력

2 0

예제 출력

00

1. 만들어진 수열의 길이와 수열의 1의 개수 
2. 탈출구 - 만들어진 수열의 길이가 n 일때
3. 로직 구현

------------------------------------------------------------------------------------------------

가장 중요하다.!!!!

재귀 함수 안에 for문이 필요 없는 경우

재귀 함수 안에 for문이 필요 한 경우

------------------------------------------------------------------------------------------------

해결

#include <iostream>

using namespace std;

char num[5];

int n,k,arry[100];

void dfs(int x,int y)

{

int i;

if(x>=n){

if(y==k){

for(i=0; i<n; i++)cout<<arry[i];

cout<<endl;

}

return;

}

if(y<k){

arry[x]=1;

dfs(x+1,y+1);

}

arry[x]=0;

dfs(x+1,y);

}

int main(){

cin>>n >> k;

dfs(0,0);

return 0;

}