[자료구조] 순환(recursion) / 반복(iteration)

이전 정리글 ↓

[자료구조] 5. 포인터(Pointer)

 

이번엔 순환에 대해 알아보자.

순환이란,

어떤 알고리즘&함수가 자기 자신을 호출해 계~속 순환하여 문제를 해결하는 프로그래밍 기법 중 하나다. 

재귀함수라고 부르기도 한다.

 

코드로 한번 알아보자.

int factorial_재귀함수(int n) {
	printf("팩토리얼 %d\n", n);
	if (n <= 1) return(1);
	else return (n * factorial_재귀함수(n - 1));
}		// 재귀함수.

 

위의 예시는 팩토리얼을 구하는 재귀함수다.

만약 int n에 3이 들어간다면?

 

1. 3은 1이 아니니 else문으로 이동

2. 3 * factorial_재귀함수(2)를 곱한다. 

→ 여기서 factorial_재귀함수(2) 를 계산하러 떠난다.

 

2-1. 2는 1이 아니니 else문으로 이동

2-2. 2 * factorial_재귀함수(1)을 곱한다.

→ 여기서 factorial_재귀함수(1) 을 계산하러 떠난다.

 

3-1. 1 <= 1은 true 이므로 1을 return 한다.

3-2. 전 단계로 돌아간다.

 

4-1. 2 * 1(factorial_재귀함수(1) return 값임) = 2

4-2. 2를 return한다.

 

5-1. 3 * 2(factorial_재귀함수(2) return 값임) = 6

5-2. 6을 return한다.

 

위의 과정을 통하여 결과값은 6이 된다. 읽어보면 생각보다 간단하다. 

식으로 정리해보면, 

factorial(3) = 3 * factorial(2)
                  = 3 * 2 * factorial(1)
                  = 3 * 2 * 1
                  = 6

요런 식으로 동작할 것이다. 

 

---

순환 ↔ 반복

컴퓨터의 되풀이 방식엔 2가지가 있다. 

 

순환 : 위의 factorial 프로그램처럼 자기자신을 다시 호출하여 문제를 해결하는 방식

반복 : for, while문처럼 전체 코드를 반복하는 방식

 

기본적으로 순환과 반복은 해결능력이 동일하다. 많은 경우 순환↔반복 간의 코드 교체가 가능할 정도로.

 

앞서 구현했던 팩토리얼 계산 프로그램을 반복문으로 바꿔보자.

int factorial_반복함수(int n) {
	int i, result = 1;
	for (i = 1; i < n; i++)
		result = result * i;
	return(result);
}

 

팩토리얼 순환구조는 위처럼 반복구조로 바꿔서 만들 수도 있다.