[Swift] Data Structure recursion / divide and conquer, D&C / 자료구조 순환, 재귀 / 분할정복

 

dbguswls030/Argorithm

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

 

순환이란?

순환은 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다. 정수 팩토리얼은 순환의 예가 될 수 있다.

 

n!은 다음과 같이 정의할 수 있다.

 

if n = 0 { n! = 1 }

else if n>=1 { n! = n * (n-1) }

 

n! 을 정의하는데 다시 팩토리얼 (n-1)!이 사용된 것에 주목하라. 이러한 정의를 순환적이라고 한다. 위 정의에 따라 n!을 구하는 함수 factorial(n)은 먼저 (n-1)!을 구하고 n을 곱하면 된다. 그렇다면 (n-1)!은 어떻게 계산할까?  

 

[swift로 작성된 코드]

 func fac(_ n: Int) -> Int{
     if n == 1 {return 1}
     else {return n*fac(n-1)}
 }

 

(n-1)!을 구하기 위해 함수는 그대로 사용하고 매개변수만 n-1로 바꾸면 된다.

 

다음은 위에 작성한 함수를 이용하여 팩토리얼 3의 답을 구하기 위한 수행 과정을 설명한다.

 

factorial(3)

= 3 * factorial(2)

= 3 * 2 * factorial(1)

= 3 * 2 * 1

= 6 

 

 

 

순환 호출의 내부적인 구현

순환 호출이 발생할 때 컴퓨터는 어떻게 처리하는지에 대한 내용이다. 어떤 함수가 다른 함수를 호출하는 것이나 자기 자신을 다시 호출하는 것이나 컴퓨터 입장에선 전혀 차이가 없다. 

 

A 함수에서 B 함수가 실행되면 B 함수가 종료된 후에 A 함수로 복귀할 수 있도록 A의 복귀 주소와 사용하던 지역 변수 등의 데이터를 모아 활성 레코드(activation record)를 준비하고 이를 스택에 저장한다. 순환호출이 중첩될수록 스택에는 활성 레코드들이 쌓이게 된다.

 

순환은 C, C++, Java 등 거의 모든 프로그래밍 언어에서 지원하지만 지역변수가 없거나 있더라도 정적으로 할당되는 일부 언어(FORTRAN, COBOL, BASIC)에서는 지원하지 않는다. 즉 함수호출마다 새로운 지역변수를 만들지 못하면 이전 호출과 구분할 수 없고 순환 호출이 불가능한 것이다.

 

 

분할 정복

 

팩토리얼의 순환호출 함수를 보면 문제를 전혀 해결하지 않고 순환 호출만 하는 것은 아니다. 전체 문제의 일부만을 해결한 다음, 순환 호출을 한다.

 

return n * fac(n-1) 이라고 할 때

n은 해결된 부분

fac(n-1)은 해결해야할 부분으로 구분할 수 있는 것이다.

 

일부가 해결되면 남은 문제는 원래의 문제보다는 쉬워진다, 더 쉬워진 문제도 동일한 방법으로 처리한다. 이러한 방법으로 어떠한 문제를 더 작은 동일한 문제로 분해하여 해결하는 방법을 분할정복(divide and conquer)라고 한다. 순환 호출이 일어날 때마다 문제의 크기가 반드시 작아져야 한다. 문제의 크기가 점점 작아지면 풀기가 쉬워지고 결국은 아주 풀기 쉬운 문제가 된다.