Algorithm 7 - Tailed recursion & Dynamic Programming

 Tail-recursion
- recursion : 자기 자신을 반복적으로 호출하는 알고리즘
recursive case, base case, termination by the base case 의 세 가지 요소가 모두 있어야 recursive algorithm을 구성할 수 있다.
base case는 unit case로 간단하게 해결할 수 있을만큼 작은 문제이다.

간단한 예로 factorial 함수를 f(n) -> n* f(n-1) 과 같은 형식으로 구성하는 것이 있다. (이 때 base case는 f(1) = 1이 된다.)
단, 이런 recursive algorithm을 수행할 때는 함수 내부의 호출이 반복적으로 일어나므로 메모리 스택에 큰 공간을 차지한다는 것에 주의해야 한다. (space complexity of O(n)) 따라서 이 방법을 사용하면 매우 간단한 문제임에도 큰 입력에 대해서는 stack overflow가 발생할 수 있음.

이런 문제를 해결하기 위해 tail recursion이라는 사용한다.
이는 다시 돌아가서 원본 함수를 계산해야 할 필요 없이 다음 스텝의 자기 자신을 호출하고, 기존 함수는 그대로 종료되는 것을 나타낸다. 따라서 stack memory에 O(n)의 공간이 필요하지 않고, 호출하고 종료한 함수의 공간을 그대로 사용할 수 있으므로 O(1)의 space complexity를 가진다.

return n*factorial(n-1) -> return factorial(n-1, n*a)로 바꾸어 계산 결과를 넣어서 리턴하는 것.

단, 두 recursive 방식은 모두 time complexity는 동일하다. (tail recursive는 time complexity에는 영향을 미치지 않는다)

Improving Quick sort
quick sort는 divide & conquer 알고리즘이며 divide, conquer, combine의 3가지 스텝으로 구성되어있다. quicksort는 이런 divide & conquer 과정에서 자기 자신을 호출하는 2 recursive function을 가지고 있다.

그러나 앞서 살펴보았듯이 divide 과정에서 비대칭적으로 나누어지게 되면 time complexity가 안좋아져 insertion sort와 비슷해진다. 따라서 pivot을 중심값으로 설정하는 방법이 중요하다.

- naive quick sort : 맨 처음/끝을 pivot으로 설정
이 경우 time complexity는 O(nlogn)에서 O(n^2)이 가능하다. space complexity의 경우 O(logn)에서 O(n) 사이가 된다. (best & worst case where the pivot is best to worst)

- Randomized quick sort : 무작위 선택, 혹은 median of 3 로 pivot을 설정
naive 방법은 만약 이미 정렬되어 있는 배열이 입력될 경우 최악의 결과를 내므로 무작위로 pivot을 설정하여 이를 방지하는 방법. 혹은 전체의 median을 설정해도 되지만 이는 전체를 스캔해야하므로 오버헤드가 지나치게 커질 수 있다.
따라서 무작위 3개의 원소를 선택하고, 이들의 중앙값을 pivot으로 사용하는 방법이 많이 사용된다. (최악의 경우를 만날 확률을 최소화하기 위해)
이런 방법을 사용하면 time complexity는 좋아질 확률이 높아지지만 space complexity에는 아무런 영향이 없다.

- Tail recursive Quick sort
space complexity를 개선하기 위해 두 번째 recursive call을 iterative로 교체하는 방법. 이렇게 되면 반복되는 부분은 tail recursive call의 공간에서 다시 실행가능하므로 공간을 절약할 수 있다. 그러나 여전히 최선일 때 O(logn) 최악의 경우에는 O(n)의 space complexity를 가진다.

이 space complexity에 가장 큰 영향을 미치는 것은 sub array의 크기이다. 왜냐하면 크기가 큰 것은 더 많이 나눠져야 하고, 더 많은 step이 필요하므로 추가적인 공간이 많이 필요하다. (O(n)에 가까워질 확률이 높다.) 따라서 크기가 큰 subarray는 그대로 두고, 작은 것을 선택하여 나누게 되면 worst case에서도O(logn)의 space complexity를 가지게 만들 수 있다.
(작은 subarray를 모두 진행하면 큰 subarray도 동일한 과정으로 계속 나누어 최대 높이를 제한하는 방식)

따라서 먼저 input array를 나누고, 나눈 sub array의 크기를 확인하고, 작은 것에 대해 recursion을 진행하게 되면 개선된 space complexity의 결과를 얻을 수 있다. 

Dynamic programming : complex problem을 smaller sub problem으로 분해하여 해결하는 것. 그러나 divide and conquer와 다른 점은 subproblem들이 독립적이지 않다는 것이다. 따라서 어떤 sub problem의 solution을 다른 sub problem에도 reuse(재적용) 할 수 있다. 이를 통해 각 subproblem은 한번만 수행되고, 연산 수행 횟수를 줄일 수 있다.

정리하면, 이를 통해 복잡한 문제도 상대적으로 쉽게 해결할 수 있다. 그리고 각 subproblem의 solution을 reuse 가능하다.

all possible combination을 고려하여 optimization problem(여러 해결책이 존재)을 해결하는데 사용된다. 그러나 이를 통해 해결해도 여전히 여러 개의 최적 솔루션이 존재할 수 있다. (AN optimal, not THE optimal)

subproblem identify -> solve each sub problem / store solution or result to reuse -> build up optimal solution for the main problem.

1. Fibonacci Sequence : F(n) = F(n-1) + F(n-2)
recursive solution을 사용하면 O(2^n)의 복잡도를 가진다. 같은 연산을 여러번 반복하기 때문에 많은 연산이 수행된다.

- Memoization (Top-down Approach)
sub problem을 위 부터 풀어가지만, 계산 결과를 캐시에 기록하여 반복적 계산을 막는다. 따라서 같은 함수/같은 input의 호출이 또 일어나면, 캐시에 저장된 값을 바로 사용한다.
따라서 어떤 값을 먼저 스택에서 확인해보고, 있다면 바로 사용, 없으면 계산하고 그 값 역시 스택에 저장한다. 이를 통해 time complexity O(n2)을 얻을 수 있다. 그러나 space complexity도 O(n)이 되므로 stack overflow가 발생할 수 있다.

- Tabulation (Bottom-up approach)
바닥의 가장 작은 sub problem부터 시작하여 최종 solution까지 만들어간다. 이 때, 각 sub problem에 대해 계산한 값들을 table에 저장하여 올라간다. 이 경우, 상위 sub problem이 필요한 하위가 모두 계산되어 있기 때문에 recursive call이 일어나지 않아도 된다.

계산법을 비교해보면, 숫자가 커질 수록 tabulation이 memoization이나 recursive보다 더 빨라진다. (tab<memo<recur)

*일반적으로 memoization이 더 간단하고 구현하기 쉽지만 많은 공간이 필요해 오버플로우가 발생할 수 있다. (작은 수의 input에 적절) tabulation은 성능이 좀 더 좋고 공간 절약이 가능하지만,(no-recursive, 큰 input도 감당 가능) 구현이 복잡하다. (많은 조건을 고려해야 함)

2. Rod-cutting problem
길이에 따라 달라지는 가격을 가지는 봉을 잘라서 팔 때, 최적의 길이를 구하는 문제 (길이/가격은 표로 주어짐)

이 경우 앞서 살펴본 recursive, memo, tabulation 세 가지 방법을 모두 적용해볼 수 있다.

- recursive
길이 n에 대해 n번 자른 각각의 경우와, 남은 길이를 다시 재귀적으로 호출하여 해결할 수 있다.
ex) r4 = (P1+recur(r3)) + (P2 + recur(r2)) + (P3+ recur(r3)) +P4(no cut) ... etc (잘라서 첫조각은 바로 팔고, 남은 조각은 더 나누는 과정을 재귀호출)

이를 통해 recursion tree를 그리면 필요한 전체 수행횟수를 쉽게 알 수 있다. 앞서 살펴본 것처럼, 동일한 함수를 계속 반복적으로 연산해야 한다는 것을 알 수 있다.

T(n) = 1 + sigma(Ti), -> O(2^n)

-memoization
가장 위의 연산부터 캐시에 값이 있으면 사용, 없으면 계산하여 push.

-tabulation
가장 아래 연산부터 계산하여 테이블에 정리,

recursion tree가 하나의 child만 가지지만, 각 단계마다 여러 호출이 발생하므로 연산만 하지 않고, 저장된 값은 여러번 리턴된다. 따라서 두 경우 모두 O(n^2)의 complexity를 가진다. (각 step마다 한번의 호출만 발생)

즉, rod cutting이나 fibonacci모두 이전 연산에서 다음 연산이 파생되므로 sub problem들이 모두 연관되어 있다. 따라서 dynamic programming으로 캐싱방식을 사용하여 계산횟수를 획기적으로 줄일 수 있다. 그러나 만약 sub problem들이 서로 독립적이라면, divide & conquer로 해결할 수 밖에 없다.