정올반 1차시

1차시에는 재귀함수에 대해서 배웠습니다.

-재귀함수란???

쉽게 말하면 함수 안에서 자기 자신을 호출하는 것입니다. 재귀함수를 사용할 때 증감식을 이용하여 호출 값을 변환해 주어야지 함수가 무한루프에 빠지지 않아요. 말로 설명하기 보다는 코드를 보면서 이해하는게 더 쉬울겁니다.

재귀함수를 이용하여 짤 수 있는 가장 보편적인 재귀함수로는 factorial이 있습니다.

factorial은 예를들어 5 factorial이면 5!이런 형식으로 나타낼 수 있는데, 그 결과값은 해당값을 1씩 줄여가며 곱하는 것이다.

ex) 5! = 5 * 4 * 3 * 2 * 1 = 120 

일반적으로 for문을 이용하여 코드를 짜면

#include <stdio.h>

int main() {

	int num, i, result = 1;
	scanf("%d", &num);

	for (i = num; i >= 1; --i)
		result = result * i;

	printf("%d\n", result);

	return 0;
}

이런식으로 코드를 짤 수 있습니다.

factorial값을 구하고 싶은 숫자부터 시작해서 값을 1씩 줄여가면서 곱해주는 것입니다.

!0과 !1의 결과값은 1이라는 조건하에 factorial 계산을 재귀함수로 구현하면 이렇게 됩니다.

#include <stdio.h>

int factorial(const int num) {

	if (num <= 1)
		return 1;

	else
		return num * factorial(num - 1);

}

int main() {

	int num;
	scanf("%d", &num);

	printf("%d\n", factorial(num));

	return 0;
} 

이 코드를 디버깅 하면 이런 방법으로 함수가 호출되고, 결과값이 저장됩니다.

예를들어 num값을 5로 설정했을 때 함수가 호출되는 법을 봅시다.

먼저 num값이 5일때, factorial(5)를 실행해 줍니다. num값이 1보다 작지 않기때문에 factorial(4)를 호출합니다. 이런식으로 num이 1보다 작을때까지 쭉쭉 함수를 호출합니다. num값이 1이 되었을때!! 다시 역방향으로 return이 시작됩니다. factorial(1)값은 위의 조건에 따라 1을 리턴하고, 그 다음 factorial(1)를 호출했던 factorial(2)함수에 값을 대입하여 factorial(2)의 값은 2, 그 다음 factorial(3)은 6이런식으로 값을 리턴해주며 계산하면 제일 처음에 호출했던 함수의 결과값을 알 수 있습니다.

그럼 재귀함수뿐 아니라 함수를 이용하여 해결할 수 있는 문제 몇가지를 더 해볼까요???

1) gcd즉, 최대 공약수를 구하는 함수를 만들어 보아요.

#include <stdio.h>

int gcd(const int num1, const int num2) {

	int max = 1, i;

	for (i = 1; i <= num1; ++i) {
		if (num1 / i == 0 && num2 / i == 0 && i > max)
			max = i;
	}

	return max;

}

int main() {

	int num1, num2;
	scanf("%d %d", &num1, &num2);
	printf("%d\n", gcd(num1, num2));

	return 0;
}

2) fibonacci수열을 재귀함수를 이용해서 계산해 보았습니다. 

fibonacci수열은 단순하게 말하자면 n-1번째 인덱스와 n-2번째 인덱스를 더해서 n번째 인덱스를 채우는 식으로 수열을 쭉 늘어가는 것입니다.

#include <stdio.h>

int arr[100] = { 0, };

int fibonacci(const int num) {

	if (num == 1)
		return 0;
	else if (num == 2)
		return 1;
	else {
		arr[num - 2] = fibonacci(num - 2);
		arr[num - 1] = fibonacci(num - 1);
		return arr[num - 2] + arr[num - 1];
	}

}

int main() {

	int num;
	scanf("%d", &num);

	printf("%d\n", fibonacci(num));

	return 0;
}

3) 입력받은 숫자부터 0까지 카운트 다운하는 재귀함수

#include <stdio.h>

int countdown(const int num) {
	printf("%-3d", num);
	if (num == 0)
		return 0;
	else
		return countdown(num - 1);
}

int main() {

	int num;
	scanf("%d", &num);
	countdown(num);

	return 0;
}

4) n의 x승을 구하는 함수

#include <stdio.h>

int f(int const n, int const x) {

	if (x <= 0)
		return 1;

	return n * f(n, x - 1);

}

int main() {

	int n, x;
	scanf("%d %d", &n, &x);
	printf("%d\n", f(n, x));

	return 0;
}

5) 약수 출력

#include <stdio.h>

int f(const int num) {

	int i;

	for (i = 1; i <= num; ++i) {
		if (num%i == 0)
			printf("%-3d", i);
	}

	return 0;
}

int main() {

	int num;
	scanf("%d", &num);
	f(num);

	return 0;
}

6) 입력받은 숫자가 소수인지 판별하기

#include <stdio.h>

int is_prime(int const num) {

	int temp = 0, i;

	for (i = 1; i <= num; ++i) {
		if (num%i == 0)
			++temp;
	}
	if (temp <= 2)
		return 1;
	else
		return 0;
}

int main(){

	int num;
	scanf("%d", &num);

	if (is_prime(num) == 1)
		printf("%d(은)는 소수 입니다\n", num);
	else
		printf("%d(은)는 소수가 아닙니다\n", num);


	return 0;
}

7) 입력받은 숫자 소인수 분해하기

#include <stdio.h>

int f(int const num) {

	int div = 2, res = num;

	while (res != 1) {
		if (res%div == 0) {
			printf("%-3d", div);
			res /= div;
		}
		else
			++div;
	}

	return 0;
}

int main() {

	int num;
	scanf("%d", &num);
	f(num);

	return 0;
}