#8 [C 자료구조] 알고리즘의 기초 of 기초: 순환(Recursion)

알고리즘에서는 순환 개념이 많이 쓰인다.

순환이란 피보나치 수열의 예시처럼 알고리즘 도중 자기 자신을 호출하는 것을 의미한다.

피보나치의 경우엔 f(n) = f(n-1) + f(n-2) 의 식을 가지므로 무려 2명의 나를 호출하는 것이다.

이건 마치...

a.k.a 순환 호출

순환의 종류

순환의 종류는 두 가지로 나뉜다.

위: 직접 / 아래: 간접

직접 순환 (Direct Recursion)은 피보나치 수열, 팩토리얼 등의 보편적인 예시라고 보면 되고

간접 순환 (Indirect Recursion)은 하나의 알고리즘이나 함수를 더 거쳐서 나오는 것이다.

 

꼬리순환 호출: n * factorial(n-1)

머리순환 호출: factorial(n-1) * n

 

예시: 팩토리얼의 순환 호출

팩토리얼은 다음과 같은 순환 단계를 거친다.

 

팩토리얼 순환 과정

결국에 마지막 단계인 factorial(1)에 가서야 순환이 멈춘다는 것을 알 수 있다.

factorial(n)은 n-1번의 순환 호출을 거친다는 것도 알 수 있다!

간단한 언어로 표현하자면

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

이렇게 재귀 함수인 factorial을 정의해볼 수 있다.

 

순환에 이용되는 스택

재귀함수는 함수가 호출 될 때 마다 이전의 함수를 닫지 않고 호출한다. 즉 factorial(400)을 한다면 factorial(1)을 도출 할 때 까지 399의 변수가 사용된다는 뜻이다. 즉 메모리 할당이 비효율 적이라는 것!

다음과 같은 언어를 쓰면 무한대 호출로 인한 스택 부족으로 작동이 중지된다.

#include <stdio.h>

void recursion();
int main(void) {
	recursion();
    return 0;
}

void recursion(){
	printf("순환중입니다\n);
    recursion();
}

그 이유는 무엇일까?

순환 호출의 내부적 구현을 뜯어보면 원인을 알 수 있다.

하나의 함수가 호출되면 호출되는 함수별로 함수 관련 정보를 활성화 레코드(Activation Record)에 저장(push)한다.

*활성화 레코드: 함수의 지역 변수와 전달되는 인자를 저장하는 공간

호출된 함수가 끝나면 운영체제의 시스템 스택에서 새로운 활성화 레코드를 pop하여 처리한다.

factorial(3)부터 Push하고 factorial(1)부터 다시 Pop하는 형식을 취한다.

여기서 재귀호출을 계속 사용하면 방금 말했던 메모리 문제가 발생한다.

따라서 우리는 이를 재귀호출 --> 반복문 으로 바꿔 주는 기능을 수행해야한다.

이를 문맥 변경(Context Switch)라 한다.

 

---

 

순환 vs 반복문

순환과 반복문의 차이를 팩토리얼을 통해 알아보자.

 

순환호출 팩토리얼	반복문 팩토리얼
n! = n*(n-1)! (n≥2) or n=1	n! = n*(n-1)*(n-2)*...*2*1
보기엔 간단하고 클레-버 해보임	보기엔 길고 스투-핏 해보임

그러나 코드를 뜯어보면 반복문이 더 간단하다는 것을 알 수 있다.

 

순환호출

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

반복문

int factorial (int n)
{
    int i, result = 1
    for ( i = 1; i <= n; i++ )
    	result = result * i;	
    return (result);
}

순환 호출은 지속적으로 factorial 함수를 불러오지만 반복문은 for문 안에서 끝내버리는 것을 발견할 수 있다.

순환문은 순환호출을 이용하지만 반복문은 for나 while을 이용한다.

대부분의 순환과 반복문은 바꾸어 작성할 수 있다.

 

그렇다면 두 방법론의 가장 큰 차이는 무엇일까?

순환호출	알고리즘의 간결성/명확성	시스템 스택으로 인한 오랜 수행 시간	스택 메모리 문제 발생 가능	팩토리얼, 거듭 제곱, 하노이의 탑
반복문	프로그램 작성 어려움	짧음	성능 우수	피보나치 수열

 

---

 

 

 

오늘은 순환의 개념에 대해 알아보았다. 다음 포스트는 이러한 순환과 반복문 개념을 실제로 적용한 사례를 볼 것이다!!

이름하야! 이 것이 순환문이다 실전편!