[C언어] 재귀함수 실습문제2

1번문제

정답

#include <stdio.h>
#include <string.h>

int isPalindrome(char* A, int n, int m) {
	if (n >= m - 1)	return 1;
	else {
		if (*(A + n) == *(A + m - 1))	return isPalindrome(A, n + 1, m - 1);
		else return 0;
	}
}
int main() {
	char A[101];
	gets(A);
	printf("%d", isPalindrome(A, 0, strlen(A)));
}

m-1대신 m을 사용하여 헷갈렸었다
문자열의 길이 - 1이 마지막 문자의 인덱스라는걸 기억하자.

2번문제

근접한 정답

#include <stdio.h>
int divide(int a, int b) {
	if (a < b) return 0;
	else
	{
		return 1 + divide(a - b, b);
	}
}
int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	printf("%d %d", divide(a, b), a - b * divide(a, b));
}

꽤나 고생한 문제, divide를 몫을 구하는 함수로 작성하는 법을 생각하지 못했다.
그러나 문제는 divide를 a,b 쌍을 반환하는 함수로 작성하라고 하였다.

함수에서 반환값이 2개 이상이 필요하면

1) 포인터를 활용하는 방법

2) 구조체를 활용하는 방법

두 가지 방법이 있다.

다음은 구조체를 활용해, 문제의 조건을 만족한 코드이다.

정답

#include <stdio.h>
typedef struct value {
	int quotient;	// 몫
	int remainder;	//나머지
}values;

values divide(int a, int b) {
	values p;

	if (a < b) {
		p.quotient = 0;
		p.remainder = a;
		return p;
	}
	values temp = divide(a - b, b);	//더미 구조체를 만들어 재귀함수를 돌린다.
	p.quotient = 1 + temp.quotient;	//재귀 호출에서 돌아가면서 몫을 1씩 증가시킨다.
	p.remainder = temp.remainder;	//나머지는 그대로 전달한다.

	return p;
}

int main() {
	int a, b, count = 0;
	scanf("%d%d", &a, &b);
	values v;
	v = divide(a, b);
	printf("%d %d", v.quotient, v.remainder);
}

생각할 게 많은 코드였다.

나머지야 재귀 호출에서 그대로 전달하면 되지만, 몫을 어떻게 전달해야할 지 막막했다.

해답은 재귀함수를 돌릴 때, 더미 구조체를 활용해서 재귀함수를 실행하고,
재귀 호출에서 몫을 1씩 증가시켜 전달하는 방식이었다.

◆ 과정 요약

1. a에서 b를 빼면서 재귀 호출
2. a < b 가 될 때 종료 (quotient = 0, remainder = a)
3. 이전 재귀호출로 돌아가면서 quotient 를 1씩 증가
4. 최종적으로 몫과 나머지만을 가진 구조체 반환

3번문제

아직 미완;;