Recursion(재귀)

재귀는 그냥 재귀다. 뭔가 반복이 계속된다 싶으면 재귀를 떠올리자.

실제 면접 문제

파이썬으로 거듭제곱 함수 pow(a, b)를 만들어 주세요. 이 함수는 두개의 정수 a, b를 입력 받아서 a의 b제곱을 리턴해야 합니다. ** 연산자를 사용하지 않고 거듭제곱 함수 선언.

의도

1. 자네가 recursion을 아나?
2. 자네가 시간복잡도를 알고 있나?
3. 자네가 효율성 있는 코드를 짤 수 있나?(메보이제이션 좀 써보시게..)

# 민우
def pow(a, b):
    result = 1
    i = 0;
    while i < b:
        result = result * a
        i = i + 1
    return result

# 엣지케이스
def pow(a, b):
    if b < 0:
        return 1.0/pow(a,-b) #엣지케이스
    result = 1
    for i in range(b):
        result = result * a
    return result

# 시간복잡도를 줄여봅니다. O(logN)
def pow(a, b):
    if b < 0:
        return 1.0/pow(a,-b) #엣지케이스
    if b == 0:
        return 1
    if b == 1:
        return a
    subPow = 0
    if b%2 == 0:
        subPow = pow(a, b/2)
        return subPow * subPow
    else:
        subPow = pow(a, (b-1)/2)
        return subPow * subPow * a

피보나치

사실 재귀는 반복문으로 하는게 거의 항상 훨 편하고 보기도 좋다.

def fibo(num):
  if num == 0:
      return 0
  if num == 1:
      return 1

  before = 0
  curr = 1

  for i in range(2, num + 1):
      temp = curr
      curr = before + curr
      before = temp
  return curr

print(fibo(40)); #102334155

동적프로그래밍

재귀 + 메모이제이션 + 효율

class Fib():
    def __init__(self):
        self.memo = {}

    def fibonacci(self, num):
        if num == 1 or num == 0:
            return num

        if not num in self.memo:
            self.memo[num] = self.fibonacci(num-1) + self.fibonacci(num-2)

        return self.memo[num]

def main():
    f = Fib()
    print(f.fibonacci(40)) # should return 55

if __name__ == "__main__":
    main()

메모이제이션 단점

시간복잡도는 대폭줄지만 공간복잡도가 늘어난다. (피보나치함수의 대입값이 n만큼일때 O(n)만큼 공간복잡도가 늘어난다.) 하지만 면접관이 공간복잡도 마저 줄여보라고 하진 않는다.