자료구조 - C언어 순환, Recursion에 대해 알아보자 (예제, 문제포함)

 오늘은 C언어에서 순환(Recursion)에 대해서 알아보겠습니다.
  팩토리얼을 구하거나 피보나치수열, 하노이 탑 알고리즘에서 순환을 이용하면 좋습니다.
순환이란 알고리즘과 함수가 수행하면서 자신을 다시 호출하여 접근하는 기법을 말합니다. 순환적으로 같은 과정을 반복할 때 주로 사용됩니다.

순환이란?

 팩토리얼 알고리즘을 한번 만들어 보겠습니다.
 n이라는 숫자가 있을 때 n이 1이 될 때까지 1씩 줄여가면서 자기 자신을 호출하여 계산하고 n이 1이 되면 1을 반환하면서 끝납니다.

 순환 알고리즘에서는 순환을 조건이 만족할 때 멈추게 해주는 것이 매우 중요합니다. 만약 멈추는 조건이 없다면 무한정 호출하여 시스템에 오류가 발생합니다. 따라서 빨간색 부분처럼 n이 1이면 1을 반환하고 함수를 멈추라는 조건이 필요합니다.

순환과 반복의 차이

 그럼 순환과 반복의 차이는 무엇일까요? 순환은 호출을 이용하고 반복문은 for나 while을 이용하여 반복합니다. 사실 같은 원리이므로 무엇을 이용해도 상관이 없지만 둘 다 사용할 줄 아는 것이 중요합니다.

실제 예시 1 팩토리얼 알고리즘

실제로 팩토리얼을 계산하는 알고리즘을 만들어 보겠습니다.
 팩토리얼이란 양의 정수 n이 주어져 있을 때 1부터 n까지 모든 수를 곱한 값을 의미합니다. n이 3이면 3*2*1=6이 되고 n=5이면 5*4*3*2*1=120이 됩니다.

#include <stdio.h>
int factorial(int n);
int main() {
	int n, r;
	printf("양의 정수 입력를 입력하세요:");
	scanf("%d", &n);
	r = factorial(n);
	printf("결과값 result = %d \n", r );
		return 0;
}
int factorial(int n)
{
	int k, v = 1;
	for (k = n; k > 0; k--)
		v = v * k;
	return(v);
}

실제 예시 2 거듭제곱 알고리즘

 거듭제곱 알고리즘을 만들어 보겠습니다.
 거듭제곱은 말 그대로 거듭제곱입니다. X^n을 구하는 알고리즘을 구현하였습니다.

#include <stdio.h>
int exp(int x, int n);
int main() {
	int x, n, r;
	printf("거듭제곱을 위한 정수 x, n 입력(x^n):\n" );
	scanf("%d",&x);
	scanf("%d",&n);
	r = exp(x, n);
	printf("result= %d \n", r);
	return 0;
}
int exp(int x, int n)
{
	if (n == 0) return (1);
	else return (x * exp(x, n - 1));
}

실제 예시 3 피보나치 함수 알고리즘

 피보나치 알고리즘을 만들어 보겠습니다.
 피보나치 함수는 앞의 두 숫자를 더하면 다음 수가 된다는 규칙이 있습니다. 
0 1 1 2 3 5 8 13 ... 이러한 규칙을 가지고 있습니다.

#include <stdio.h>
int fib( int n );
int main(){
int n, r,i;
printf("정수 n 입력:");
scanf("%d", &n);
for (i = 0; i < n; i++){
r = fib(i);
printf("%d ", r); }
printf("\n");
return 0;
}

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

실제 예시 4 하노이탑 알고리즘

가장 어려운 하노이 탑 알고리즘을 만들어 보겠습니다.
 하노이 탑의 규칙은 기둥이 3개 있을 때 A에 있는 원판을 C로 옮기면 되는데 작은 원판 위에 큰 원판이 올라갈 수 없다는 규칙이 있습니다. 그래서 B라는 기둥을 잘 이용해야 합니다. 원판의 개수와 상관없이 A에서 C로 옮길 수 있습니다. 참조를 활용하면 쉽게 할 수 있습니다.

#include <stdio.h>
void hanoi_tower(int n, char from, char tmp, char to)
{
if( n == 1 )
printf("원판 1을 %c 에서 %c으로 옮긴다.\n",from,to);
else {
hanoi_tower( n-1, from, to, tmp );
printf("원판 %d을 %c에서 %c으로 옮긴다.\n",n, from, to);
hanoi_tower(n-1, tmp, from, to);
}
}
int main()
{
int disk_no; // 원반 수
printf("하노이 타워의 원반 수 입력: ");
scanf( "%d", &disk_no );
printf( "*** 하노이 타워를 옮겨라 A에서 C로 ***\n" );
hanoi_tower ( disk_no, 'A', 'B', 'C');
return 0;
}

 

 오늘은 함수의 순환에 대해서 알아보았습니다. 많은 사람이 반복문을 이용하는 것은 잘하는데 순환은 조금 어려워하는 경향이 있습니다. 비슷한 원리로 작동하지만, 순환이 도움이 되는 때도 있습니다. 둘 다 알아놓으면 적절히 잘 이용할 수 있을 것입니다.

 

가장 비슷한 조건문과 반복문이 궁금하다면?

2020/08/26 - [전공지식/자료구조 와 알고리즘] - 자료구조 - C언어 조건문에 대해 알아봅시다 (if, else if, 중첩 if, switch )

자료구조 - C언어 반복문에 대해 알아봅시다 (if, else if, 중첩 if, switch )

2020/08/25 - [전공지식/자료구조 와 알고리즘] - 자료구조 - C언어 반복문에 대해 알아보자

자료구조 - C언어 반복문에 대해 알아보자