[코드] 재귀함수 (Recursive function)

재귀함수 란?

아래의 예를 들어 설명을 해보겠다.

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
“재귀함수가 뭔가요?”
“잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네.
그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.
“재귀함수가 뭔가요?”
“잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을…

출처 : https://namu.wiki/w/재귀함수

위의 예 처럼 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다.

이것을 Python 함수로 이용하게 된다면, 재귀 함수라고 하는 것이다.

코드

def retrieve(x):
    return retrieve(x)

retrieve(x)

위의 코드와 같이 함수 안에 자기 자신 함수를 다시 사용하는 것 이다.

주의 : 참고로 Python은 함수 깊이 제한이 기본 1000으로 되어 있어서, 대충 995회 쯤 재귀를 하면 뻗어버린다.

재귀함수 도출 방법?!

그러면 어떻게 하면 쉽게 재귀함수로 코드를 작성하여 도출 할 수 있을까??

방법은 점화식(재귀식)을 알면 쉬워진다.

간단한 예로 피보나치 수열을 예를 들어보겠다.

피보나치 수열의 점화식(재귀식)은 아래와 같다.

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2) 이다.

그래서 재귀함수를 작성하는 경우, f(0) 와 f(1)과 같은 조건은 따로 만들어주고 해당 값을 return 한다.
또한 f(n)과 같은 식은 함수의 return으로 f(n-1)+f(n-2)로 하면 된다.

코드로 예를 들어보겠다.

# f(0) = 0
# f(1) = 1
# f(n) = f(n-1) + f(n-2)
# 함수 정의를 f(n)으로 정의하여 fib(n)
def fib(n):
    # f(0) = 0 이라는 조건
    if n == 0:
        return 0
    # f(1) = 1 이라는 조건
    elif n == 1:
        return 1
    
    # return 값은 f(n) = f(n-1) + f(n-2) 이므로 fib(n-1) + fib(n-2)
    return fib(n-1) + fib(n-2)

print(fib(10))

이런 식으로 점화식(재귀식)을 이용하여 문제를 해결하면 수월해 진다.

점화식 도출 방법?!

규칙을 찾는다.

예) 피보나치 수열

이런 식으로 규칙을 찾으면 점화식을 얻을 수 있다.

---

필자 왈..

점화식 규칙 찾는다고 하는데…. 그 규칙을 찾기 너무 어렵네요…

누가 쉽게 찾을 수 있는 방법 알고 있다면 댓글로 부탁드립니다!!