순환을 알아 보기에 앞서서 순환과 반복은 다르다는 것을 알아두자!

순환 : 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
반복 : 말그대로 반복하여 문제를 해결하는 기법

순환

순환(recursion)이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.

순환은 많은 문제들을 해결하는데 독특한 개념적인 프레임 워크를 제공한다.
본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다.

팩토리얼 문제가 가장 잘 알려진 순환 문제이다. 다음 코드를 살펴보자.

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

위 함수를 살펴보면 함수 내부에서 자기 자신을 불러온다는 것을 알 수 있다.
이처럼 자기 자신을 불러오는 함수를 재귀함수(recursive function)이라고 한다.
더 나아가서 위 함수가 진행되는 순서를 살펴보자

int factorial(3)
{
      if(n == 1) return 1;
      else return (3 * factorial(3 - 1));
}
//-> factorial(2)를 호출한다.
int factorial(2)
{
      if(n == 1) return 1;
      else return (2 * factorial(2 - 1));
}
//-> factorial(1)을 호출한다.
int factorial(1)
{
      if(n == 1) return 1; // 조건문이 참이므로 1을 return한다.
      else return (n * factorial(n - 1)); 
}

이와 같이 factorial(3)에서 시작하여 factorial(2), factorial(1)을 순차적으로 호출하는 것을 알 수 있다

순환 호출의 내부적인 구현

main()에서 factorial(3)을 호출했을 때 시스템 스택을 확인해보면

다음과 같이 순환의 호출이 중첩될수록 시스템 스택에 활성 레코드들이 쌓이게 된다.
· 활성 레코드: 함수를 위한 시스템 스택에서의 공간

순환의 알고리즘

recursive 함수는 자기 자신을 순환적으로 호출하는 함수이다.
만약 함수 내에 순환호출을 멈추는 부분이 없다면 시스템 스택을 다 사용할 때까지 순환적으로 호출되다가 결국 에러를 내면서 멈출 것이다. → 순환을 break 시켜주는 코드가 반드시 필요하다.

순환 ↔ 반복

반복문을 사용하면 일정한 횟수 동안 반복을 시키거나 어떤 조건에 만족될 때까지 걔속해서 반복시킬 수 있다. 많은 경우 이러한 반복 구조는 문제를 간결하고 효율적으로 해결할 수 있으며 우리가 익숙한 방식이다. 하지만 어떠한 경우에는 반복을 사용하면 할 수록 문제가 복잡해지는 경우가 있다. 이런 경우 순환이 매우 좋은 해결책이 될 수 있다.

다시 한번 말하지만 순환과 반복은 다른 개념이다.

순환의 원리

순환은 분할 정복(divide and conquer)을 사용한다.
· 분할 정복(divide and conquer): 주어진 문제를 저 작은 동일한 문제들로 분해하여 해결하는 방법
※ 순환 호출이 일어날 수록 문제의 크기가 작아진다

순환은 문제를 나누어 해결하는 분할 정복 방법을 사용한다.