[Algorithm] 재귀함수와 반복문

https://github.com/1000zoo/data-engineering-dev-course/blob/main/week1/day1.ipynb

재귀함수

• 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 것
• 모든 재귀알고리즘은 반복문으로도 구현 가능하다

Recursive vs Iterative

• 둘 다 시간 복잡도는 같다.
• 다만, 재귀의 경우, n이 커질 수록 함수 호출이 많아져, 효율은 떨어질 수 있다.
• Recursive의 장점은, 사람 관점에서 코드가 간결해보이고 구현하기 쉽다는 점이다.
  • 좀 더 직관적이다.

피보나치 수열 예제

Iterative

def iterative(x):
    if x <= 1:
        return x
    f0 = 0
    f1 = 1
    f2 = 1

    for _ in range(1, x):
        f2 = f0 + f1
        f0 = f1
        f1 = f2

    return f2

• 변수가 여러개 필요하여 간결해보이진 않는다.
• 하지만 효율성 측면에서는 Recursive 방식보다는 좋다.
  

  

Recursive

def recursive(x):
    if x <= 1:
        return x
    return recursive(x - 1) + recursive(x - 2)

• 코드가 매우 간결하다.
• 수식으로 표현해도 코드와 유사해 보인다.
• 하지만, 수가 커질 수록 시간이 훨씬 오래걸린다.
  
• 예를들어 x = 4의 경우, recursive(3) + recursive(2), 총 2개의 함수가 우선 호출되는데, recursive(3) 내부에서도 recursive(2)가 또 다시 호출될 것이므로, 중복된 계산을 하는 함수스택이 여러번 쌓이게 된다.
• 성능상의 불리한 점이 있다