Recursions and Dynamic Programming <4-1>

<< 4주차 Lecture Note 1번째>>

• Repeating Problems and Divide and Conquer
• Recursion
• Recursions and Stackframe

---

 

Repeating Problems and Divide and Conquer

프로그래밍에서 Recursion(재귀) 라는 용어는 보통 어떤 함수를 콜하는 과정에서 동일한 함수를 다시 콜하는 것에 쓰인다.

문제 해결 관점에서 말하면, 큰 단위의 문제를 특정 기준으로 나누고, 다시 나누어진 문제들을 동일한 기준으로 반복해서 나누며

하나의 문제를 점점 작은 단위로 만들고, 그를 통해 해결하는 과정을 일컫는다.

그래서 재귀가 사용되는 문제를 Repeating Problems, 그 문제의 해결을 Divide and Conquer 이라고 칭한다.

 

아래에 어떤 회사의 예산을 책정하는 문제가 있다고 해보자.

 

회사는 여러 부서의 구성으로 이루어진다. 위 그림에서는 Company A는 영업, 제조, R&D 부서로 이루어져있다.

그리고 회사 A의 각 부서는 다시 하위에 여러 부서를 둔다. 그림에서는 영업 부서에서 서울,부산,대전 지사를 두고 있다.

 

예산이 어느정도 필요한가의 문제를 회사 A 전체로 보면 600만원이 필요하지만,

부서별로 나눠 보면 영업,제조,R&D 에서 각각 100만, 300만, 200만원이 필요하다.

다시 영업 부서를 각 지역 지사로 나누면, 서울은 10만원, 부산과 대전은 그외 금액이 필요하다.

 

Recursion은 위 그림처럼, 문제 해결을 위해 같은 기준으로 문제를 큰 단위에서 작은 단위로 나누면서 해결하고자 하는 것이다.

이 과정을 프로그래밍하면, 특정 메서드 안에서 동일한 메서드가 재실행 되고, 그 실행으로부터의 반환값으로 문제를 해결하는 구조가 된다.

 

위 그림의 예산 책정 문제를 프로그래밍한 코드를 보자.

class Department:
    dept = [sales, manu, rnd]
    
    def calculateBudget(self):
        sum_budget = 0
        for itr in range(0, numDepartments):
            sum_budget = sum_budget + dept[itr].calculateBudget()
        return sum_budget

 

위 코드는 정확한 코드는 아니지만, 재귀함수 구현을 위한 부분만 보인 것이다.

코드를 보면, calculateBudget 이라는 함수 안에서 동일한 함수가 다시 사용되고 있고,

그를 통해 각 부서의 sum_budget을 산출한다.

회사 A의 하위 부서의 sum_budget은 다시 각 부서의 하위 부서의 sum_budget을 return 받아 계산하는 구조다.

---

Recursion

Recursion을 다시 명확히 정의해보자.

Recursion 이라는 것은 self-similar 한 repeating item을 다루는 프로그래밍 함수다.

여기서 self-similar 라는 것은 앞서 언급한 repeating problem을 말하는데, 동일하지만 더 작은 크기의 형태를 말한다.

 

Recursion의 대표적은 프로그래밍 형태는 위에서 본 코드와 같이,

특정 함수 안에서 동일한 함수를 다시 콜하는 형태이며, 그 때 입력되는 파라미터는 함수를 다시 콜 할 때의 파라미터 크기가 더 작다.

또한, 특정 조건을 만족하면 콜한 함수를 빠져나오고 return 값을 주는 코드가 포함되어야 한다.

 

Recursion을 이용한 가장 대표적인 코드가 피보나치 수열 구현이다. 코드를 보자.

def Fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    intRet = Fibonacci(n - 1) + Fibonacci(n - 2)
    return intRet

 

피보나치 값을 구하는 함수 안에서 동일한 피보나치 함수가 반복 실행하도록 구현되어 있다.

그리고, 상위 피보나치 함수 안에서 실행하는 하위 피보나치 함수의 파라미터는 n 보다 작은 n-1과 n-2로 표현되어있다.

이처럼 Recursion은 함수 내부에서 같은 함수를 쓰면서 더 작은 파라미터를 사용하고, 그를 통해 문제의 단위를 더 작게 만든다.

위 코드에서 if 문은 함수를 재귀하지 않고 탈출하도록 만드는 탈출 조건이 된다.

 

---

Recursions and Stackframe

위의 피보나치 수열을 구현한 코드를 실행하면, Recursion의 흐름은 아래와 같다.

 

 

아래 방향으로의 화살표는 Recursion이 실현되는 흐름이고, 위 방향으로의 화살표는 각 함수에서 상위 함수로 return 하는 값이 된다.

 

이런 Recursion의 흐름은 Stack을 이용해서도 표현이 되며, 실제 컴퓨터가 Recursion을 실행할 때에는 Stack 구조로 실행한다.

위 흐름을 스택프레임으로 보면 아래와 같다.

 

\(\quad\) 1) Fibonacci(4)가 입력되면, 스택프레임은 그 파라미터 4를 local variable로 저장(Push)한다.

\(\quad\) 2) Recursion에 의해 Fibonacci(3)이 실행되고, 스택프레임은 그 파라미터 3을 Push한다.

\(\quad\) 3) 동일하게 Fibonacci(2)가 실행되고, 파라미터 2를 Push한다.

\(\quad\) 4) 동일하게 Fibonacci(1)이 실행되고, 파라미터 1을 Push한다.

\(\quad\) 5) Fibonacci(1)은 바로 값 1을 return 하므로, 동시에 스택프레임에서 pop 되어 삭제된다.

\(\quad\) 6) Fibonacci(0)이 실행되고, 바로 값 0을 return 하므로 동시에 스택프레임에서 pop 되어 삭제된다.

\(\quad\) 7) 이제 스택프레임에 있던 Fibonacci(2)가 return 되면서 스택프레임에서 pop 되어 삭제된다.

\(\quad\) 8) Fibonacci(3)이 return 되고, pop 되어 삭제된다.

\(\quad\) 9) 코드에 의해 그림 오른쪽 부분의 Fibonacci(2)가 실행되면서 앞의 과정대로 Push와 pop이 발생한다.

\(\quad\) 10) 최종적으로 Fibonacci(4)가 값 3을 return 하면서 스택프레임은 빈 스택이 된다.

 

이처럼 Recursion은 스택 구조로 push와 pop을 컴퓨터 자체적으로 진행하기 때문에, 컴퓨터의 메모리를 함께 사용하게 된다.

때문에, 재귀가 많아지는 경우 컴퓨터 메모리의 부족으로 작업 환경에 따라서 프로그래밍에 영향을 주거나, 큰 비용을 지불할 수 있기 때문에

프로그래밍 시 사용 가능여부를 충분히 고려해줘야 한다.

참고로 파이썬은 이런 메모리 문제를 방지하기 위해 Recursion을 1,000회로 제한을 두고 그 이상 재귀가 실행되면 오류를 발생시킨다.