[c] 재귀

함수의 재귀적 호출의 이해

 

재귀함수 예시

void Recursive(int num)
{
	if(num<=0)
    	return;
    printf("Recursive call! %d\n",num);
    Recursive(num-1);
    
}

int main(void){
	Recursive(3);
}

 

재귀 활용

#include <stdio.h>

int Fibo(int n){
	printf("func call param %d\n",n);
    
    if (n==1)
    	return 0;
    else if (n==2)
    	return 1;
    else
    	return Fibo(n-1)+Fibo(n-2);
}

inr main(void){
	Fibo(7);
    return 0;
}

피보나치 수열 예시

 

하노이 타워

하노이 타워 문제 해결

1. 작은 원반 n-1개를 a에서 b로 이동
2. 큰 원반 1개를 a에서 c로 이동
3. 작은 원반 n-1개를 b에서 c로 이동

이를 코드로 옮기면 다음과 같다.

#include <stdio.h>

void Hanoi(int num, char from, char by, char to){
	if(num==1)
   	{
    	printf("원반 1을 %c에서 %c로 이동\n",from,to);
    }
    else
    {
    	Hanoi(num-1,from, to, by);
        printf("원반 %d을 %c에서 %c로 이동\n",num,from,to);
        Hanoi(num-1,by,from,to);
    }
 }
 
 int main(void){
 	Hanoi(3,'a','b','c');
    return 0;
 }

 

 

#백준 25501

문제에서 예시로 준 재귀함수 양식을 참고했습니다.

num으로 입력받을 횟수를 받고 while문을 통해 개수만큼 list에 문자들을 입력받았습니다.

입력받은 문자열을 함수에 넣은 반환값과 함수 실행횟수를 저장한 전역변수 play룰 반환해주었습니다.

#include <stdio.h>
#include <string.h>
int play = 0;

int recursion(const char *s, int l, int r){
    play++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(const char *s){
    return recursion(s, 0, strlen(s)-1);
}

int main(){
    int num;
    scanf("%d",&num);
    char list[1001] ={0};
    while(num--){
        play = 0;
        scanf("%s",list);
        
        int p = isPalindrome(list);
        printf("%d ",p); // 1
		printf("%d\n",play);
    }
}

#백준 2747

위 예시를 응용해서 작성해보았는데 답은 맞았지만 시간 초과가 발생했다.

아마 재귀함수 특성상 반복문보다 시간이 더  오래 소요되어서 그런듯한데...

비슷한 질문을 한 글들의 답변을 확인해보니 동적계획법을 사용하라는 의견이 있는데...맞는지 잘 모르겠다

우선 답은 맞았으니 따로 여쭤보아야지...

#include <stdio.h>

int Fibo(int n){   
    if (n==0)
    	return 0;
    else if (n==1)
    	return 1;
    else
    	return Fibo(n-1)+Fibo(n-2);
}

int main(void){
	int num;
	scanf("%d",&num);
	printf("%d",Fibo(num));
    return 0;
}

#백준 11729

정답이 나왔다고 하기에도 민망한 코드...

위 예시의 식을 응용했다. 다만 실행횟수인 cnt를 하노이 함수 자체에서 새면 실행 횟수를 먼저 출력할 시 전역변수값이 0인채로 출력되기 때문에... 어떻게 처리할까 고민하다가 출력을 안하는 하노이 함수를 하나 더 만들어서 cnt만 새주는 용으로(...) 따로 출력해주었다. 뭔가 더 다른 방법이 있을 것 같지만... 생각나는 방법이 없었다......(^^;)

#include <stdio.h>
int cnt = 0;

void Hanoi(int num, int from, int by, int to){
	cnt++;
	if(num==1)
   	{
    	printf("%d %d\n",from,to);
    }
    else
    {
    	Hanoi(num-1,from, to, by);
        printf("%d %d\n",from,to);
        Hanoi(num-1,by,from,to);
    }
 }
 
void Hanoi_cnt(int num, int from, int by, int to){
	cnt++;
	if(num==1)
   	{
    	
    }
    else
    {
    	Hanoi_cnt(num-1,from, to, by);
        Hanoi_cnt(num-1,by,from,to);
    }
 }

 int main(void){
	int play = 0;
	scanf("%d",&play);
	Hanoi_cnt(play,1,2,3);
	printf("%d\n",cnt);
 	Hanoi(play,1,2,3);
    return 0;
 }