알고리즘 | 재귀(Recursion)

재귀함수 문제를 아직 몇 개 못 풀어보긴 했지만, 지금까지 느낌으로는 재귀함수를 활용한 풀이는 마법같이 느껴지기도 한다. 하위 문제가 올바르게 해결된다는 가정만 정확히 한다면, 하위 문제의 구체적인 해결 방법을 코드로 직접 짜지 않아도 컴퓨터의 빠른 연산이 자동으로 해결해준다. 처음에는 '이게 말이 돼?'라는 생각이 든다. 때문에 직관적이지 않지만, 제대로 습득한 사람들에게는 매우 유용한 도구가 될 것이라 생각된다. 

 

하위 문제에 대한 해결책이 이미 정의되어 있다고 "가정"하는 것은 재귀의 핵심 철학 중 하나입니다. 재귀의 아름다움은 그것이 문제를 단순화하는 방식에 있습니다. 복잡한 문제를 여러 작은 조각으로 나누면, 각 조각을 해결하는 것은 종종 훨씬 더 쉽습니다. 재귀는 이러한 단순화를 반복적으로 적용하여 문제의 해결책을 찾아갑니다.

 

---

재귀 (Recursion)

컴퓨터 과학에 있어서 재귀(再歸, recursion)는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출(recursive call)의 형태로 많이 사용된다. (출처: 위키피디아)

 

재귀 알고리즘과 수학적 귀납법의 관계

재귀적 알고리즘의 올바름을 증명할 때 수학적 귀납법을 사용하기 적합합니다. 재귀 함수의 각 호출이 올바르게 동작한다는 것을 보이기 위해, 기본 케이스가 올바르게 동작한다고 가정하고 그 다음 단계가 올바르게 동작함을 증명합니다. 이는 수학적 귀납법의 접근 방식과 매우 유사합니다.

,, by chatGPT

 

수학적 귀납법 

GPT가 얘기해주듯 수학적 귀납법을 활용하면 재귀함수 구현 & 복잡한 재귀함수 해석에 도움이 된다고 한다. 그러나 고딩때 배운 수학적 귀납법을 잊고 살아온 (나 포함) 대부분 사람들을 위해 잠시 정리하자면.. 

 

연역논증의 일종이며, 완전귀납법이라고도 한다. (출처: 나무위키)

 

왜 증명 과정이 타당하다면 결론까지 타당하다고 하는가? 

 

출처: 위키피디아

수학적 귀납법의 정의이다.

 

쉽게 설명하면 1부터 n까지 받는 함수 f(n)이 어떤 조건에 성립함을 증명한다고 할 때, f(1) 성립 확인 -> f(2) 성립 확인 -> f(3)  ... 으로 가는 것은 절차지향적 접근 방식이다. 절차지향적 접근은 직관적이라는 장점이 있다. 누구도 이를 받아들이는데 어려움을 느끼지 않는다. 

 

한편, 다음과 같이 접근하는 방식도 있다. 

 

1. f(1)이 성립함을 증명
2. f(n)이 성립하면 f(n+1)도 성립함을 증명

=> 모든 자연수 n에 대해 f(n)이 성립한다는 결론

 

이를 조금 변형해서 다음과 같이 쓸 수도 있다. 

 

1. 기본 단계 (base step): f(n)이 성립함을 증명
2. 귀납 단계 (inductive step): f(k)가 성립하면 f(k+1)도 성립함을 증명

=> n 이상의 모든 자연수에 대해 f(n)이 성립한다는 결론

 

귀납 단계의 구조를 잘 보면 가정 + 증명의 구조이다. 

 

일단 알 수 없는 문제(f(k)의 성립여부)는 성립한다고 '가정'하고, 만약 f(k)가 성립할 때 f(k+1)도 성립하는지에 집중하는 것이다. 

이게 성립하면 앞에서 가정했던 문제도 자연스럽게 성립한다. 

 

이를 수학적 귀납법이라고 하고, 이러한 접근법은 처음에는 직관적이지 않을 수도 있지만, 경우에 따라서 매우 간단하게 문제를 해결할 수 있다는 장점을 갖고 있다.

 

 

재귀 알고리즘 구현

재귀 알고리즘은 두 부분(base condition + general condition)으로 구성되어 있다. 

 

1. base condition(base case)은 재귀 호출 없이 직접 해결될 수 있는 가장 작은 문제이다. 동시에, 탈출 조건이기도 하다. base condition이 정의되어 있지 않으면 무한 재귀에 빠질 수 있다. 

2. general condition(recursive case)은 재귀를 통한 문제 해결 부분이다. 큰 문제를 더 작은 부분으로 나누어, 그 중 하나 또는 그 이상을 재귀를 호출하여 해결한다. 

 

올바른 재귀 함수는 반드시 1) base condition으로 수렴해야 하며, 2) base condition에 닿았을 때는 자기 자신을 호출하지 않고 종료되어야 한다.

 

 

재귀 알고리즘이 이용되는 가장 대표적인 예시가 팩토리얼 문제이다. 

def fact(n):
    # base condition
    if n == 0: 
        return 1
    # general condition
    else:
        return n * fact(N-1)

 

 

만약 N == 3이라면, 동작 순서는 다음과 같다. 

 

 

수학적 귀납법과 연계하여 이해하기

위 팩토리얼 구현 코드의 구조를 잘 보면, 위에서 살펴본 수학적 귀납법과 비슷하게 생겼음을 알 수 있다. 

 

그럼 해당 코드가 피보나치 함수를 잘 구현했음을 보이기 위해, 수학적 귀납법 방식으로 이해를 해보자.

 

1. 기본 단계: 더 이상 나눌 수 없는 기본 단계(n)가 올바르게 동작하는지 증명
2. 귀납 단계: 임의의 단계(k)가 올바르게 동작한다고 가정하고, 그 다음 단계(k+1)가 올바르게 동작함을 증명

 

기본 단계
- 우리는 n = 0인 경우, 0! = 1 임을 알고 있다. 따라서 문제 없다. 

귀납 단계: 
- 임의의 자연수 k에 대해, fact(k)가 k!을 올바르게 반환한다고 가정하자.
- fact(k+1)를 호출하면, 이는 (k+1) * fact(k) 를 반환한다.
- 앞선 가정에 따르면, fact(k)는 k!을 반환한다. 따라서 fact(k+1)은 (k+1)*k!, 즉 (k+1)! 을 반환한다. 

=> 그러므로 모든 자연수 n에 대해, fact(n)은 n!을 반환한다. 

 

단순히 fact(n) 함수 내부에 갇혀서 생각하지 말고, fact(n)이라는 함수 자체가 정상적으로 동작한다고 치고 그렇다면 fact(n+1) 까지 잘 동작하는 건지를 생각해야한다. 

 

실제로 팩토리얼 함수는 다음과 같이 정의된다.

 

 

재귀 구현 vs 반복문 구현

- 모든 재귀 알고리즘은 반복문을 통해, 동일한 동작을 수행하도록 구현할 수 있다. 

 

- 반복문을 통한 구현은 절차적 사고, 재귀 함수를 통한 구현은 귀납적 사고라고 할 수 있다. 

 

- 성능은 반복문을 통한 구현이 낫고, 가독성은 재귀함수를 통한 구현이 낫다. (함수 호출이 리소스를 잡아먹는 연산이므로 메모리, 시간적으로 손해)

 

► 재귀함수 사용할 때는 스택 오버플로우(stack overflow)를 주의

재귀 함수가 자기 자신을 부를 때 메모리의 스택 영역에 함수에 대한 정보가 누적된다.
때문에 스택 메모리가 작게 제한된 곳에서 알고리즘 문제를 재귀로 풀게 된다면 런타임 에러가 발생하기도 한다. 

>> http://www.tcpschool.com/c/c_memory_stackframe

 

- 그러나 요즘처럼 하드웨어가 좋은 시대에는 반복문이 성능이 더 좋다는게 크게 유의미하지 않은 수준이라고 한다. 때문에 반복문으로 구현하기엔 너무 복잡한 문제의 경우에는 가독성이 더 좋은 재귀를 선호하는 경우도 많다고 한다. 

 

 

 

재귀함수가 비효율적인 대표적인 예시: 피보나치 함수

피보나치 함수는 재귀함수 구현 < 반복문 구현 < 다이나믹 프로그래밍 구현 순으로 효율적이다.