[TIL] 재귀 함수 Recursion Function Python

하노이의 탑을 풀기 전에 재귀 함수의 개념 먼저 정리한다 

 

재귀 Recursive 
반복 Iterative 

 

 

재귀 함수 Recursion Function 

자기 자신을 다시 호출해 작업을 수행하는 방식
자신의 로직을 내부적으로 반복

단, '함수 자신' 이 아니라 자기 자신과 똑같은 함수'를 호출하는 것이다! 혼동 주의

반복문으로 구현 가능한 로직은 모두 재귀함수로 구현이 가능하고 
그 반대도 가능하다 

 

* Base Case 더 이상 문제를 쪼갤 필요가 없는, 종료 조건에 도달한 경우

* Recursive Case 문제를 작은 문제들로 나누어 해결하는 과정 

 

 + 09/18 WED 나중에 읽어봐야지 https://velog.io/@eddy_song/you-can-solve-recursion

 

예시01 팩토리얼 함수

 

1. 팩토리얼 반복문으로 구현

def factorial(N):
    # Total 초기값 1 로 설정 
    # N 도 곱해줘야 하니 N+1 까지 
    total = 1
    for i in range(1, N+1):
        total *= i
    return total

num = int(input())
print(factorial(num))

 

2. 팩토리얼 재귀 함수로 구현 

def factorial2(N):
    if N == 0: return 1
    return (N * factorial2(N-1))

num = int(input())
print(factorial2(num))

 

예시02 피보나치

1. 피보나치 반복문으로 구현

def fibonacci(n):
    if n <= 1:
        return n
    
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a+b
    return b

if __name__ == '__main__':
    print(fibonacci(10))

 

2. 피보나치 재귀 함수로 구현

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

if __name__ == '__main__':
    print(fibonacci(10))

 

재귀 함수의 장점

변수를 여러 개 만들 필요 없다

반복문을 사용하지 않아도 되기 때문에 코드가 간결해진다

스택 형태로 구현된 재귀 트리는 함수 호출의 흐름을 시각화하는 데 유용할 수 있다 

 

재귀 함수의 단점

함수의 호출이 스택에 쌓이게 되고, 차례대로 값을 반환하기 전에는 계속 메모리 공간을 차지하고 있다

( 스택 오버플로우가 발생할 수 있다 -> 무한 루프에 빠지지 않도록 종료 조건을 명확하게 설정해줘야 한다 )

함수의 호출이 반복적으로 일어나기 때문에, 반복문을 사용하는 것보다 느리다 

 

 + 09/12 THU

 방금 ㅅㅎ님이 알려줬는데 아까 같이 풀었던 재귀 트리는 스택 형태로 구현할 수 있다고 한다! 싱기방기 

 

 + DO IT 알고리즘입문 CH06 읽다가 하노이의 탑 코드를 봐버렸다