[C언어][자료구조] 순환(recursion)

※ 이 글은 C언어 기준으로 작성하였습니다.

순환(recursion)이란...

---

 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법입니다. '재귀'라고도 부릅니다.

 

 

러시아 인형 '마트료시카'를 아신다면 그것 또한 좋은 예라고 할 수 있겠습니다.

void example()
{
	.
	.
	.
	.
	return example(); //자기자신을 출력
}

recursion을 구성할 때는 무한반복이 일어날 수 있기 때문에

 

매개변수를 바꾸고 조건문을 사용하여 반복을 제한합니다.

 

몇 가지 예시를 통해 알아봅시다.

---

 factorial(팩토리얼)

#include <stdio.h>

int factorial(int n)
{
	if(n <= 1) return (1); //반복 종료 조건 
	else return (n * factorial(n-1));
}

int main()
{
	printf("%d\n",factorial(5)); // 출력결과 120 
	return 0;
}

 

else return (n * factorial(n-1));

factorial 함수의 출력으로 factorial이 포함되어 있지만,

 

매개변수는 원래 함수보다 -1 된 값이 들어있습니다. 

 

factorial(5)라면 출력값이 5 * factorial(4)입니다.

 

if(n <= 1) return (1); //반복 종료 조건 

n이 1보다 작거나 같을 때, 함수는 1을 출력하고 반복을 종료합니다.

 

factorial(5) = 5 * factorial(4) = 5 * 4 * factorial(3)= 5 * 4 * 3 * factorial(2)

 

= 5 * 4 * 3 * 2 * factorial(1) = 5 * 4 * 3 * 2 * 1 = 120

 

거듭제곱

#include <stdio.h>

double power(double x, int n)
{
	if(n==0) return 1; //반복 종료 조건 
	else if ((n%2)==0)
		return power(x*x, n/2);
	else return x*power(x*x, (n-1)/2);
 } 
 
 double power2(double x, int n) //좀 더 간단한 버전
{
	if(n==0) return 1; //반복 종료 조건 
	else return x * power2(x, n-1);
 } 
 
 int main()
 {
 	printf("%f\n",power(4,3)); //출력값 64 
 	printf("%f\n",power2(4,3)); //출력값 64 
 	return 0;
 }

---

보다보니 다음과 같은 의문이 생깁니다.

 

for문을 사용하면 되는데 왜 굳이 recursion을 사용할까요?

 

사실 수행 시간과 메모리 사용량을 따져보면 for문이 더 효율적입니다.

 

그럼에도 recursion을 사용하는 이유는

 

프로그래밍하기 간단하고 이해하기 쉽기 때문입니다.

 

power2 함수를 for문으로 나타낸다면,

double power2(double x, int n)
{
	int i;
	double result = 1.0;
	
	for(i=0;i<n;i++)
	{
		result = result * x;
	}
	return result;
 } 

이와 같이 라인 수가 늘어납니다.

 

recursion과 비교해보면 표현이 더 복잡해집니다.

 

물론 함수가 간단하여 이해하는데 무리는 없지만

 

함수가 복잡해질수록 recursion의 진가를 느낄 수 있을 겁니다.