순환(recursion, aka.재귀)

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

 

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

순환은 자기 자신을 호출하는 것

순환
순환(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)을 호출했을 때 시스템 스택을 확인해보면

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

 

아직 스택에 대해 이해가 덜 되었다면 이 글을 다시 읽고 오자!

2021/01/11 - [Fundamental/Data Structure] - 스택

스택

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

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

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

 

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

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

 

분할 정복에 대해 자세하게 알고 싶다면 이 글을 읽어보자.

2021/01/18 - [Fundamental/Algorithm] - 분할 정복 알고리즘 (Divide-and-conquer)

분할 정복 알고리즘 (Divide-and-conquer)