재귀함수 시리Z

아래 8가지를 재귀함수를 사용하여 구현해 보고자 한다. 

1. 합 구하기

2. 높은 자리수부터 차례로 출력

3. 낮은 자리수부터 차례로 출력

4. 최댓값 구하기

5. 하노이 탑 문제

6. 최대공약수

7. 최소공배수

8. 특정 문자가 몇 번 나타나는지 구하기

 

1. 합 구하기

#include <stdio.h>
#pragma warning(disable:4996)
int sum(int n){
 	if (n==1)	return 1;	// base case
	else 		return n+sum(n-1);
}

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

2. 높은 자리수부터 차례로 출력

#include <stdio.h>
#pragma warning(disable:4996)
int print_digits(int n) {
	if (n < 10)	printf("%d\n", n);	//if (n/10==0)
	else {
		print_digits(n / 10);
		printf("%d\n", n % 10);
	}
}

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

3. 낮은 자리수부터 차례로 출력

#include <stdio.h>
#pragma warning(disable:4996)
int print_digits(int n) {
	if (n < 10)	printf("%d\n", n);	//if (n/10==0)
	else {
		printf("%d\n", n % 10);
		print_digits(n / 10);		//여기 순서를 바꿈
	}
}

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

4. 최댓값 구하기

#include <stdio.h>
#pragma warning(disable:4996)

int MAX(int arr[], int i) {
	if (i == 0)	return arr[0];	//base case
	else {
		int max = MAX(arr, i - 1);
		max = arr[i] > max ? arr[i] : max;
		return max;
	}
}

int main() {
	int num;
	int arr[20];
	scanf("%d", &num);
	for (int i = 0; i < num; i++) {
		scanf("%d", &arr[i]);
	}
	printf("%d", MAX(arr, num - 1));
	return 0;
}

5. 하노이 탑 문제

*하노이탑 문제는 비재귀에 의해 작성하라면 고난도의 문제지만 재귀에 의하면 훨씬 쉽게 풀리는 문제의 좋은 예다. 

#include <stdio.h>
#pragma warning(disable:4996)
void hanoi(int n, char from, char aux, char to) {
	if (n == 1)	printf("%c %c\n", from, to); //1번
	else {
		hanoi(n - 1, from, to, aux);		//2번
		printf("%c %c\n", from, to);		//3번
		hanoi(n - 1, aux, from, to);		//4번
	}
}
int main() {
	int num;
	scanf("%d", &num);
	hanoi(num, 'A', 'B', 'C');
	return 0;
}

설명

 

2번에서 n개의 원반 중 맨 아래의 가장 큰 원반을 제외한 윗부분의 n-1개의 원반을 보조 말뚝으로 옮긴다.

이때 재귀호출의 매개변수를 조정해야 하는데, 현 목표 말뚝이 비어 있으므로 이를 보조 말뚝으로, 원반들을 현 보조 말뚝으로 옮겨야 하므로 이를 목표 말뚝으로 각각 설정한다.

원반들이 현출발 말뚝에 놓여 있으므로 출발 말뚝은 그대로다.

 

3번에서 출발 말뚝 맨 아래의 원반을 목표 말뚝으로 옮긴다. (출력으로 명시해 줌)

 

4번에서 앞서 2번 수행 결과 보조 말뚝에 머물고 있는 n-1개의 원반을 모두 목표 말뚝으로 옮긴다.

이때도 재귀호출의 매개변수를 조정해야 하는데, 원반들이 현 보조 말뚝에 놓여 있으므로 이를 출발 말뚝으로, 현 출발 말뚝이 비어 있으므로 이를 보조 말뚝으로 각각 설정한다. 원반들을 현 목표 말뚝으로 옮기고자 하므로 목표 말뚝은 그대로다.

 

4번이 실행되고 나면 모든 원반들이 목표 말뚝으로 옮겨진다. 

 

명령문 1번은 베이스 케이스로서, 재귀가 진행됨에 따라 n의 숫자가 점점 줄어 1이 된 시점에 재귀에 의존하지 않고 직접 해결하는, 즉 한 개의 원반을 직접 옮기는 작업이다. 

와 진짜 천잰가..?

6. 최대공약수

#include <stdio.h>
#pragma warning(disable:4996)

int gcd(int a, int b) {
	if (a == 0)	return b;
	else if (b == 0)	return a;
	else	return gcd(b, a % b);
}

int main() {
	int a, b;
	scanf("%d %d", &a, &b);
	printf("%d",gcd(a, b));
	return 0;
}

7. 특정 문자가 몇 번 나타나는지 구하기

#include <stdio.h>
#include <string.h>
#pragma warning(disable:4996)

int TEST(char arr[],char ch,int len, int i) {
    if (i == len) return 0;

    if (arr[i] == ch)
        return 1+ TEST(arr, ch, len, i + 1);

    else {
        return TEST(arr, ch, len, i + 1);
    }
    
}


int main() {
    int len = 0;
    char arr[101];
    char ch;
    
    scanf("%s", arr);
    getchar();
    len = strlen(arr);

    scanf("%c", &ch);

    printf("%d",TEST(arr, ch, len,0));
    return 0;
}

 

생각해 볼 문제

return에 재귀함수가 들어가는 경우와 재귀함수가 return에 들어가지 않는 경우의 차이.

(어떤 경우에 들어가고 어떤 경우에 안 들어가는지?)

#include <stdio.h>
#pragma warning(disable:4996)

int gcd(int a, int b) {
	if (a == 0) return 5;
	else	return gcd(b-b, a); //else gcd(b-b,a);와의 차이?
}

int main() {
	int a, b;
	scanf("%d %d", &a, &b);
	printf("%d",gcd(a, b));
	return 0;
}