이번 챕터에서는 recursion 재귀에 대해 공부해보려고 한다. 자료구조론에서 중요하게 다루게 될 tree가 재귀로 구현되기 때문에 잘 알아둬야한다! 순서는 다음과 같다.
- 재귀함수로 코드 짜는 방법
- binary recursion (이진재귀)
그럼 시쟉🌟
1. Recursion (재귀)
1-1. 재귀함수란?
재귀는 자체 코드 내에 자기자신을 불러오는 것을 의미한다. 재귀의 예시로 팩토리얼(!)을 들 수 있는데, 재귀함수를 이용한 팩토리얼은 다음과 같다.
위 사진을 보면, n! 안에 (n-1)! 즉 팩토리얼이 포함되어 있는 것을 확인할 수 있다.
만약 n에 4를 대입하면 4 x 3! 이 되고 3!은 3 x 2! 을 불러오는 과정을 반복하여 결국 n = 0이 되어 함수를 불러오는 과정이 종료된다. 이후에는 숫자를 삽입해 계산하는 과정이 진행되는데, 가장 마지막에 불러진 fac(0)부터 계산되며 가장 먼저 불러온 fac(4)가 가장 마지막에 계산된다.
이를 보면 알 수 있듯이 재귀는 후입선출 즉 stack구조를 사용한다!
1-2. 재귀함수로 코드 짜는 방법
이와같이 재귀함수를 이용하여 코드를 작성하는 일이 많다. 코드를 짤 때 어떤 식으로 짜야 프로그램이 죽지 않을까?
우선, 첫 if문에서는 basecase를 잘 작성해야한다.🌟
Basecase란 해당 반복문을 끝내는 조건을 말한다. 더이상 자기자신을 부르지 않아도 되는 조건을 작성하는 것이다. 위에서 예시를 들었던 factorial로 예를 들어보면 n = 0 일 때 1을 리턴하는 것이다. 1을 리턴하며 재귀는 종료된다. 이런 종료조건을 잘 쓰는 것이 무한루프 굴레로 빠지지 않는 중요한 방법이다.
basecase를 잘 작성하는 것 뿐만 아니라, 반복 할수록 basecase에 가까워져야한다. factorial로 예를 들어보면, 처음에 n = 5 라고 하게 되면 반복을 할수록 n은 4, 3, 2, 1, 0으로 줄어들어 마침내 basecase인 0에 도달한다. 반복 할수록 n이 커지게 된다면 무한루프에 빠지고 말 것이다.
또 한 가지 주의해야 할 점이 있다. 맨 위 사진을 보고 허전한 점이 있지 않았는가? 바로 빠뜨릴 수 있는 조건을 최대한 챙기는 것이다. 만약 어떤 사용자가 factorial의 n에 -3을 넣는다면 어떻게 될까? 종료조건이 n = 0일 때 뿐이라서 무한루프를 돌게 될 것이다. 그래서 fac함수에는 n >= 0 이라는 조건을 추가해야 한다. 일어날 수 있는 모든 사건의 경우의 수를 생각해 프로그램이 정상적으로 돌아갈 수 있도록 코드를 작성하는 것이 중요하다.
1-3. Tail Recurse
부차적으로 recurse의 한 종류인 tail recurse에 대해 간단하게 살펴보려고 한다.
tail recursion (꼬리재귀)란, 재귀함수의 실행 결과가 연산에 사용되지 않고 바로 반환되게 함으로써 이전 함수의 상태를 유지할 필요가 없도록 재귀함수를 작성하는 것을 의미한다.
이는 콜 스택이 깊어질수록 메모리 오버헤드가 발생하는 재귀함수의 문제점을 해결하기 위한 재귀호출방식이다.
<일반적인 재귀함수>
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n -1);
}<꼬리재귀함수>
function factorialTail(n, a) {
if (n === 1) return a;
return factorialTail(n - 1, a * n); // 재귀함수가 연산에 쓰이지 않음
}
이에 대한 예시로는 array reversal이 있다.
참고로 array reversal은 배열 순서를 뒤집는 것이다. 예를 들어 1 3 4 9 8 이라는 배열이 있었다면 이를 8 9 4 3 1 로 바꾸는 것이다.
아래 코드로 살펴보자
// 1) non-recursive methods
Algorithm IterativeReverseArray(A, i, j):
Input : An array A and nonnegative integer indices i and j
Output : The reversal of the elements in A starting at index i and ending at j
While i < j do
Swap A[i] and A[j]
i = i + 1
j = j - 1
return
// 2) 🌟recursive methods =================
Algorithm ReverseArray(A, i, j):
Input : An array A and nonnegative integer indices i and j
Output : The reversal of the elements in A starting at index i and ending at j
if i < j then
Swap A[i] and A[j]
ReverseArray(A, i + 1, j - 1) //이렇게 함수 마지막단계에서 recursion되는 경우 >> tail recurse
returnrecursive method를 보면 i < j일 때 i++, j--이면 basecase인 i>=j에 가까워지므로 잘 짠 코드라고 할 수 있다.
1-4. linear recursion? binary recursion?
재귀함수가 무언가를 반복하는 프로그램에서 가치 있는 함수라는 것은 사실이다. 그럼 항상 효율적인 방법일까? 다양한 함수를 예시로 설명해 볼 것이다.
▶ Pow Function ============================
위와 같이 재귀로 코드를 작성한다면 재귀를 y번 호출해야 하므로 O(n)이 된다.
여기서 시간복잡도를 줄일 수 있는 방법이 있는데, 바로 binary recursive algorithm을 사용하는 것이다! 아래 사진을 보자.
참고로 even은 짝수, odd는 홀수이다.
위 사진만으로는 어떻게 작동되는지 보기 힘드므로 p(2,6)을 예시로 구해보자.
p(2,6)은 n이 even이므로 제일 아래에 따라 (p(2,3))^2이 된다. p(2,3)은 odd이므로 가운데 식에 따라 2x(p(2,1))^2이 된다. p(2,1)은 odd이므로 가운데에 따라 2x(p(2,0))^2이 된다.
p(2,0)은 n이 0이므로 1이다. 위로 천천히 대입해보면 ,
p(2,1) = 21 = 2, p(2,3) = 24 = 8, p(2,6) = 64가 된다. 정답은 64라는 것을 도출할 수 있다.
이 방법으로 하면 확실히 과정이 간단해지는 것을 알 수 있다. 이를 알고리즘 코드로 나타내면 아래와 같다.
Algorithm Power(x,n):
Input : A number x and integer n = 0
Output : The value x^n
if n = 0 then
return 1
if n is odd then
y = Power(x, (n-1)/2)
return x*y*y
else
y = Power(x,n/2)
return y*y위 코드를 보면 pow 안의 n이 1/2씩 되며 basecase인 n = 0으로 수렴하는 것을 확인할 수 있다. 1/2 된다는 것은 log₂n에서 -1씩 줄어드는 것이다. 그러므로 이를 O(log₂n)으로 나타낼 수 있다.
이렇게 linear recurse를 이용하여 러닝타임을 확실히 단축시킬 수 있다. binary recurse로 러닝타임을 단축시킬 수 있는 또 다른 예시를 살펴보자.
▶숫자배열에서 원하는 수 찾기 ========================
16개의 숫자 요소가 있고, 이 안에서 원하는 수를 찾는 알고리즘을 짤 때 binary recurse는 확실히 효율적인 방법이다. 단, 수가 오름차순이나 내림차순이어야 한다.
위 사진은 22를 찾는 과정을 담은 것이다. 맨앞부터 찾아내면 worst case(찾는 수가 37인 경우)의 경우 n개의 수를 모두 조사해야 하므로 O(n)이 된다. 그러나 위 사진처럼 하면 O(log₂n)이 된다.
▶22를 찾는 상황이라는 가정하에 binary search
- 전체 중 가운데값 확인
- 가운데값이 찾는 값이면 운 좋은 거
- 중간값보다 찾는 값이 크면 중간 기준 왼쪽값(작은값)은 다 버리고, 남은 수 중 중간값을 찾아 반복
이렇게 하면 4번의 비교면 충분하기 때문에 한개씩 비교하는 것 (O(n))보다 훨씬 효율적이게 된다. 이 예시까지만 보면 재귀함수를 쓰는 것이 마냥 좋다고 생각할 수 있는데, 그렇지 않은 경우도 있다. 아래 예시를 살펴보자.
▶Binary sum =============================
정수의 배열 A에서 A[i]부터 n개의 수를 더하는 함수가 있다고 가정하자. 이때 편의를 위해서 , i = 0, n = N이라고 가정한다. 아래 알고리즘을 보면,
Algorithm BinarySum(A, i, n) :
Input : An array A and integers i and n
Output : The sum of the n integers in A starting at index i
if n = 1 then
return A[i]
return BinarySum(A, i, n/2) + BinarySum(A, i + n/2, n/2)이를 도식화 하면 다음과 같다.
위 사진을 보면 알 수 있듯이 재귀함수 호출 수는 2⁰ + 2¹ + 2² + 2³ = 2n - 1이 된다. 앞에서부터 차례로 더해가면 n번이면 되는데 이렇게 하면 2n-1이 된다.
이 경우는 O(n) -> O(n)인 경우이며, binary recursion을 사용한다고 항상 시간복잡도가 좋아지는 게 아니라는 것을 보여준다. 더 나빠질 수도 있다. 다음 예시가 그런 경우이다.
▶Computing Fibonacci Numbers =========================
바로 피보나치수열이다. 피보나치는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 의미한다. 피보나치를 binary recursion을 사용한 알고리즘을 살펴보면,
Algorithm BinaryFib(k):
Input : Nonnegative integer k
Output : The kth Fibonacci number Fĸ
if k = 1 then
return k
else
return BinaryFib(k-1) + BinaryFib(k-2)로 작성할 수 있다. 더 와닿을 수 있게 k가 5인 상황을 예시로 위 코드를 이용해보면
n₅ = n₃+ n₄
n₄= n₂+ n₃
n₃= n₁+ n₂
n₂= n₀ + n₁이다.
n₀과 n₁은 각각 n₀ = 1, n₁= 1이므로 n₂은 2, n₃은 1+2=3, n₄는 2+3=5, n₅ 는 3+5=8이 된다. 이는 결국 2^(k/2)번 불러내므로 O(2^(k/2))가 된다. 이렇게 되면 러닝타임이 너무 길어져 사용할 수 없는 프로그램이 된다.
이런 경우는 linear recursion을 사용하는 것이 효율적이다.
Algorithm LinearFibonacci(k):
Input : A nonnegative integer k
Output : Pair of Fibonacci numbers(Fĸ - Fĸ-₁)
if k = 1 then
return (k,0)
else
(i,j) = LinearFibonacci(k - 1)
return(i+j,i)이렇게 하면 k-1번의 재귀호출이 있으므로 O(n)이 된다.
이렇게 linear recurse를 쓰는 것과, binary recurse를 쓰는 것은 개인이 선택해야 할 몫이다. 정해진 방법은 없다고 교수님께서 말씀하심 !!
사실 경우에 따라 세 갈래, 네 갈래로 갈라지는 것도 있긴 하다. 그렇게 되면 O(log₃), O(log₄)가 될 수도 있는 것이다. 하지만 이렇게 되면 코드의 복잡도에 비해 러닝타임이 눈에 띄게 줄지는 않아서 여기까지는 통상적으로 잘 다루지 않는다고 한다! 그냥 O(log₂)가 되는 경우 까지만 열심히 복습해두면 된다😊