C - 자료구조 순환

순환이란 ?

어떠한 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.

일반적으로 반복문보다 느리다.

반복문을 쓰면 코드가 개판이 되지만 재귀로 적으면 깔끔해지는 코드를 쓰는데 활용 된다

 

#include <stdio.h>

int factorial(int n){
   if(n==1){
       return 1;
   }
   else if(n>=2){
       return (n + factorial(n-1));
   }

}

int main(void){
    int b=0;
    scanf("%d", &b);
    printf("%d", factorial(b));
}

1+2+3+...+n을 계산하는 순환 함수이다.

함수명이 factorial인 이유는 n! 함수 먼저 풀면서 공부해서 그런거니 신경 쓰지 마

아무튼 factorial함수를 잘 보면 자기 자신을 다시 호출해서 계산한다

코드를 천천히 정리해보면

int factorial(int n){
   if(n==1){
       return 1;
   }
   else if(n>=2){
       return (n + factorial(n-1));
   }
   //n에 5를 입력했을 경우
   //return (5 + factorial(4) + factorial(3) + factorial(2) 이후 n==1이 되서 1)
   // 5+4+3+2+1 로 1부터 n(5)를 계산함

함수 안에서 또 함수 자신을 호출하며 n이 1이 됐을때 1을 리턴하며 함수가 끝난다.

이 짧은 구문에서 알 수 있는 사실은

1. 자기 자신을 계속 호출하여 1부터 n을 더하는 연산을 for, while문이 아닌 함수로 표현할 수 있다.

2.대신 그 순환이 멈추는 조건까지 설정해줘야 한다는 것을 유의하자

 

1부터 n까지 곱하는 n! 팩토리얼 연산을 함수로 표현해보자

#include <stdio.h>

int factorial(int n){
   if(n==1){
       printf("factorial(1)\n");
       return 1;
   }
   else if(n>=2){
       printf("factorial(%d)\n", n);
       return (n * factorial(n-1));
   }

}

int main(void){
    int b=0;
    scanf("%d", &b);
    printf("%d", factorial(b));
}

출력 결과

5 //5를 입력함
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
120

 

* 순환 호출의 내부적인 구현에 대해 정리해보자

위에서 보여준 팩토리얼 예제로 알아보자면프로그래밍 언어에서 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일하다. 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수와 지역변수를 스택으로 할당 받게 되는데 이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드라고 칭한다. 이러한 준비가 끝나면 호출된 함수의 시작 위치로 점프하여 수행을 시작한다.

만약 호출된 함수가 자기 자신이라면 자기 자신의 시작 위치로 되돌아가게 된다. main()에서 factorial()을 호출 하였을때 factorial()안에서 다시 facotrial()이 호출되면 시스템 스택은 아래와 같아진다

[1] factorial(3) { if( 3<=1 ) return 1; else return (3*factorial(2)); }	[2] factorial(2) { if ( 2<=1 ) return 1; else return (2*factorial(1)); } --------------------------- factorial(3) {  if( 3<=1 ) return 1; else return (3*factorial(2)); }	[3]  factorial(1) { if( 1<= 1) return 1; } -------------------------- factorial(2) { if ( 2<=1 ) return 1; else return (2*factorial(1)); } --------------------------- factorial(3) {  if( 3<=1 ) return 1; else return (3*factorial(2)); }
[4]  factorial(2) { if ( 2<=1 ) return 1; else return (2*factorial(1)); } --------------------------- factorial(3) {  if( 3<=1 ) return 1; else return (3*factorial(2)); }	[5]  factorial(3) {  if( 3<=1 ) return 1; else return (3*factorial(2)); }	[6]

위의 표가 factorial(3)의 호출중의 시스템 스택 변화를 나타낸거다.

번호 순서대로 보기 좋게 정리했으니 이해하기 쉽게 잘 정리했다고 칭찬 해주세요

 

이제 순환 알고리즘의 구조에 대해서 살펴보자

 

int factorial(int n){
   if(n==1) return 1; //순환을 멈추는 부분
   else return (n * factorial(n-1)); //순환 호출을 하는 부분
}

만약 순환을 멈추는 if(n==1) return 1;구문이 없으면 factorial(-1), factorial(-2), factorial(-3) ... factorial(-1334) 등으로 끝 없이 순환 호출을 하며 오류를 발생 시킨다.

* 꼭 순환을 멈추는 구문을 넣어주도록 하자 !!

 

반복의 경우 수행속도가 순환에 비해 빠르지만 순환적인 문제에 대해서 반복문을 이용해서 프로그램을 작성하면 아주 어려워질 수 있다!

 

N까지의 정수들 중 3의 배수의 합을 구해서 반환하는 순환함수를 작성해보았다.

int factorial(int n){
   if(n==0){
       return 0;
   }
   else if(n % 3 == 0){
       return n + factorial(n-1);
   }
   else {
       return factorial(n-1);
   }
}

factorial 함수에 int형 변수 n을 매개변수로 보내

n = 0 일 경우 0 을 return

n을 3으로 나눴을 때 나머지가 0 이면 현재 n의 값을 return하면서 factorial(n-1)의 값을 다시 순환 호출

n이 그 외의 경우라면 n-1의 값을 다시 순환 호출 한다.

그래서 n이 6이라고 가정했을 경우 

return 6 + factorial(5)
return 6 + factorial(4)
return 6 + factorial(3)
return 6 + 3 + factorial(2)
return 6 + 3 + factorial(1)
return 6 + 3 + factorial(0)
return 6 + 3 + 0

의 형식으로 순환하는 것이다.

 

재귀함수의 중요 포인트는 2가지이다

1. 종료 조건

2. 중요포인트

위 사항들을 고려해서 생각해보자

 

*피보나치 수열

피보나치 수열이란 ? 1,2 번째 항은 0과 1로 지정해주고 그 후 n번째 항은 값은 n-1번째항 + n-2번째항이다.

종료 조건은 n이 0일때 0을 리턴하는 것과 n이 1일때 1을 리턴하는 것이다.

중요 포인트는 f(n) = (n-1) + (n-2) 인 것을 알 수 있다.

#include <stdio.h>

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

int main(void){
    int a;
    scanf("%d", &a);
    printf("%d", fib(a));
}

사용자에게 a값을 입력 받아서 그 항까지의 수열 값을 출력하는 프로그램이다.

7을 입력했을때 값은 13이 출력이 된다.

1, 1, 2, 3, 5, 8, 13 ... 이기에

7번째 항은 13이며 함수의 결과 값이 올바르다는 것을 확인할 수 있다 

 

*하노이의 탑

void hanoi_tower(int n, char from, char tmp, char to) {
	if (n == 1) {
		//from에 있는 한개의 원판을 to로 옮긴다.
	}
	else {
		/*
		1.from의 맨 밑의 원판을 제외한 나머지 원판들을 tmp로 옮김
		2.from에 있는 한개의 원판을 to로 옮긴다
		3.tmp의 원판들을 to로 옮긴다.
		*/
	}
}

하노이의 탑의 조건을 토대로 코드를 짜기전 이렇게 설계할 수 있다.

이것들을 바탕으로 코드를 짜보면

#include <stdio.h>

void hanoi_tower(int n, char from, char tmp, char to) {
	if (n == 1) {
		//from에 있는 한개의 원판을 to로 옮긴다.
		printf("원판 1을 %c에서 %c으로 옮긴다.\n", from, to);
	}
	else {
		//1.from의 맨 밑의 원판을 제외한 나머지 원판들을 tmp로 옮김
		hanoi_tower(n - 1, from, to, tmp);
		//2.from에 있는 한개의 원판을 to로 옮긴다
		printf("원판 %d을 %c에서 %c으로 옮긴다.\n", n, from, to);
		//3.tmp의 원판들을 to로 옮긴다.
		hanoi_tower(n - 1, tmp, from, to);
	}
}

int main(void) {
	hanoi_tower(4, 'a', 'b', 'c');
	
}

출력 결과

원판 1을 a에서 b으로 옮긴다.
원판 2을 a에서 c으로 옮긴다.
원판 1을 b에서 c으로 옮긴다.
원판 3을 a에서 b으로 옮긴다.
원판 1을 c에서 a으로 옮긴다.
원판 2을 c에서 b으로 옮긴다.
원판 1을 a에서 b으로 옮긴다.
원판 4을 a에서 c으로 옮긴다.
원판 1을 b에서 c으로 옮긴다.
원판 2을 b에서 a으로 옮긴다.
원판 1을 c에서 a으로 옮긴다.
원판 3을 b에서 c으로 옮긴다.
원판 1을 a에서 b으로 옮긴다.
원판 2을 a에서 c으로 옮긴다.
원판 1을 b에서 c으로 옮긴다.