Recursive Function and Recurrence Relation

Recursive Function(재귀 함수)와 Recurrence Relation(점화식) 이해하기.

어떤 문제는 앞 단계의 결과가 다음 단계를 결정하는 구조를 가지는 경우가 있음.
이러한 문제는 점화식(Recurrence Relation)으로 표현(update euqation이라고도 부름)하기 좋고,
이를 그대로 코드로 옮길 때는 재귀 함수(Recursive Function)가 자연스럽게 사용됨.

 

참고로, recursion은 Turing-complete 시스템에서 반복(loop)과 동등한 계산 표현 수단으로 사용됨.

https://dsaint31.me/mkdocs_site/CE/ch08/ce08_programming_language/

BME

 

Turing completeness는 어떤 계산 모델이나 시스템이 이론적으로 모든 계산 가능한 문제를 표현·수행할 수 있는 능력을 의미함.프로그래밍 언어에서는 재귀나 반복, 조건 분기 등을 통해 Turing-complete한 구조를 제공함으로써, 이론적으로 어떤 알고리즘이든 구현할 수 있는 언어인지 판단하는 기준으로 사용됨.

---

1. Recurrence Relation(점화식)이란?

Recurrence Relation 은 어떤 값이 바로 이전 단계 또는 여러 이전 단계의 값으로 정의되는 수학적 관계식임.

예를 들면 다음과 같음:

• $f(n) = f(n-1) + 1$
• $f(n) = f(n-1) + f(n-2)$

Recurrence relation은 계산 과정을 단계별로 표현하므로, 같은 구조를 가진 recursive function으로 그대로 구현될 수 있음.

 

수학에서의 relation에 대한 정의는 다음을 참고:

https://dsaint31.tistory.com/680

[Math] Relation

---

2. Recursive Function(재귀 함수)가 Recurrence Relation과 잘 맞는 이유

Recursive Function은 자기 자신을 다시 호출하는 방식으로 실행됨.

 

Recurrence Relation 을 통해 단계 간 관계를 수학적으로 정의되므로,

Recursive Function은 해당 관계를 실제 실행 흐름으로 구현할 수 있음.

 

주의할 점으로는

• Recursive Function에는 반드시 Base Case(기저조건, 종료조건) 가 필요함.
• Base case가 없다면 함수가 끝없이 호출되다가 stack overflow 에러를 일으키게 됨.

---

3. Recurive function의 예: Collatz Sequence

Collatz 수열은 다음 규칙을 반복하여 생성되는 수열임.

1. 양의 정수 $n$ 에서 시작
2. $n$ 이 짝수이면 $n \to n/2$
3. $n$ 이 홀수이면 $n \to 3n + 1$
4. 이 과정을 반복하면 언젠가는 1에 도달한다고 알려짐 (수학적 증명은 아직 되지 않음.)

예를 들어 6에서 시작하면:

6 => 3 => 10 => 5 => 16 => 8 => 4 => 2 => 1

 

참고로, 단순해 보이지만
Collatz sequence는
"모든 양의 정수가 반드시 1에 도달하는지"는
아직 수학적으로 증명되지 않은 미해결 문제임.

---

4. Collatz Sequence을 재귀 함수로 구현하기

다른 이름으로는 Collatz conjection, 3n+1 problem, Hailstone sequence(우박수열) 이라고도 불림.

 

Collatz Sequence의 규칙은 다음과 같은 Recurrence relation으로 표현됨:

$$a_{k+1} =
\begin{cases}
\frac{a_k}{2}, & \text{if } a_k \text{ is even} \\
3a_k + 1, & \text{if } a_k \text{ is odd}
\end{cases}$$

 

위의 Recurrence relation을 그대로 파이썬 코드로 옮긴 구현은 다음과 같음:

def collatz(n):
    """
    Collatz sequence를 재귀적으로 출력하는 함수
    """
    print(n, end=" => ")

    # 종료 조건(Base Case)
    if n == 1:
        return

    # 다음 단계 계산 및 재귀 호출(Recursive Case)
    if n % 2 == 0:
        collatz(n // 2)
    else:
        collatz(3 * n + 1)

---

실행 예시

$n=6$ 인 경우 다음과 같은 결과를 보이게 됨.

6 => 3 => 10 => 5 => 16 => 8 => 4 => 2 => 1

---

5. Disadvantages of Recursion

Recursive function은 구조적으로 깔끔하지만, 다음과 같은 단점이 존재.

1) 스택 메모리(Stack Memory) 사용 증가

재귀가 깊어질수록 호출 스택이 누적되어 메모리 사용량이 늘어납니다.

2) 재귀 깊이 제한(Recursion Depth Limit)

메모리 사용량이 지나치게 늘어나는 것을 막기 위해 파이썬은 약 1000단계의 재귀 깊이 제한을 가지고 있으며, 이를 초과하면 다음 오류가 발생함.

RecursionError: maximum recursion depth exceeded

3) 중복 계산으로 인한 비효율성

예를 들어 피보나치 수열의 단순 재귀 구현은 동일한 값을 여러 번 계산하여 매우 느려질 수 있음.
(이 문제는 반복문이나 memoization 기법을 사용하면 해결 가능함.)

4) 실행 흐름 이해의 어려움

재귀 호출이 여러 단계로 중첩되면 프로그램의 실행 순서를 직관적으로 파악하기 어려워짐.

---

같이보면 좋은 자료들

https://dsaint31.tistory.com/492

[Python] recursive call : Fibonacci Sequence (and dynamic programming)

https://dsaint31.tistory.com/326

[Math] Geometric Series (등비급수 or 기하급수)

https://m.blog.naver.com/kim-nan-hee/223128801841

[프로그래머스][Python] 콜라츠 수열 만들기 문제 풀이

---