[재귀 함수] recursive function

재귀함수란? 

재귀 함수란 함수 안에서 자기 자신의 함수를 다시 호출하는 것을 말합니다. 

재귀 함수는 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 끝나야 그 앞의 함수를 종료하는 구조이기 때문에 스택 구조입니다.

반복문으로도 구현가능한데 굳이 재귀함수를 쓰는 이유는 뭘까요? 왜냐하면 재귀함수로 구현했을 때 직관적이기 때문에 이해하는데 쉽기 때문입니다.

파이썬에서는 재귀함수의 최대 깊이가 존재합니다. 따라서 계속 호출하는 경우 인터프리터에서 재귀함수 깊이 오류를 발생시킵니다.

 

def recursive_fuc():
    print("재귀함수 호출")
    recursive_fuc()
recursive_fuc()

 

재귀함수 구현해보기 - 파보나치 수열

# Fibonacci (순환): O(2^n)

def fibo(n):
  if n <= 1:
    return n;
  return fibo(n-1) + fibo(n-2);

print(fibo(30))

파보나치 수열이란 n[0] = 0 n[1] = 1, n[2] =1, n[3] = 2, n[4] = 3, n[5] = 5와 같이 n-1 과 n-2 값을 더하는 수열 문제입니다.

이 처럼 재귀함수로 구현하게 되면 직관적이고 이해하기 쉽도록 코드를 작성할 수 있습니다.

 

 

재귀 함수 문제점

 하지만 이해하기 쉽다고 재귀함수만 이용해서 코드를 구현해서는 안됩니다. 재귀 함수의 문제점은 메모리 저장이라는 문제가 있습니다.

파보나치 수열 같은 경우 숫자가 커지면서 계산해야 하는 양이 늘어나고 이전 값들은 버리는 현상이 생겨 테이블 형식으로 데이터를 저장했을 때 보다 시간이 훨씬 오래 걸리는 현상이 발생합니다. 예를 들어서 위에서 구현한 코드에서 100번째 숫자로 구현하도록 바꿀 경우 시간이 엄청 걸리는 것을 확인할 수 있습니다.

 

반복문 - 파보나치 수열

# Fibonacci (반복): O(n)
def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

수학적 점화식을 바로 옮기지 않고 변수를 통해 그 값을 저장하고 더하는 형식이여서 재귀함수로 구현했을 때 보다 직관적이지 않지만 재귀 함수의 메모리 낭비 문제를 해결할 수 있습니다.

 

내용정리

재귀함수로 구현하면 수학적 점화식을 코드로 옮겨 간결하고 이해하기 쉽다는 장점이 있습니다. 하지만 반복적인 호출로 인해 재귀함수의 데이터가 메모리에 차곡차곡 쌓이게 되고 그로 인해 처리하는 시간이 오래 걸리는 문제가 발생하였습니다.

파보나치 수열에 대한 경우 반복문으로 처리해서 문제를 해결했지만 꼬리재귀를 이용해서도 문제를 해결할 수 있습니다.

 

꼬리 재귀 파이썬 구글 검색 보러가기

🔎 꼬리 재귀 파이썬: Google 검색