14. 재귀함수 / 피보나치수열 / 조기리턴과 리스트 평탄화

혼공파 57 ~ 59 강

 

1. 재귀 함수

# 재귀 함수
# 자기자신을 호출하는 함수

## 팩토리얼 연산
# n! = n * (n-1) * (n-2) * ... * 1

## - 반복문으로 구현
def factorial(n):
  output = 1
  for i in range (1, n + 1):
    output *= i
  return output

print(factorial(5)) # 120
  
## - 재귀함수로 구현
# 수열의 점화식으로 구현
# 팩토리얼의 점화식
# 1! = 1
# (n이 2 이상의 수일 때) n! = n * (n-1)!

def facrotial(n):
  # 1! = 1
  if n == 1:
    return 1
  # (n이 2 이상의 수일 때) n! = n * (n-1)!
  elif n >= 2:
    return n * factorial(n - 1)

print(factorial(5))

# 함수는 호출될 때 스택을 만들고 리턴할 때 스택을 제거한다.

---

2. 피보나치수열 / 재귀함수의 메모화

# 피보나치 수열
# a_1 = 1
# a_2 = 1
# a_n = a_{n-1} + a_{n-2}

def f(n):
  if n == 1:
    return 1
  elif n == 2:
    return 1
  else:
    return f(n-1) + f(n-2)

print(f(3)) # 2
print(f(4)) # 3
print(f(5)) # 5
print(f(35)) # 9227465 계산하는데 시간이 꽤 걸림

# 그래프 - 트리구조로 함수가 실행

# 메모화 
# 한번 계산한 결과를 미리 메모해 두고 트리가 진행 될때 저장해둔 값으로 바로 넣을 수 있도록함

memo = {1: 1, 2: 1}
def f_m(n):
  if n in memo:
    return memo[n]
  else:
    temp = f_m(n-1) + f_m(n-2)
    memo[n] = temp
    return temp

print(f_m(35)) # 9227465 바로 결과가 나옴

---

3. 조기 리턴 / 리스트 평탄화

# 조기리턴(ealry return)
# 함수의 리턴 키워드는 함수 내 코드 진행의 마지막에만 사용하는 것이 이전 트렌드였으나, 지금은 그렇지 않다.

memo = {1: 1, 2: 1}
def f_m(n):
  if n in memo:
    return memo[n]   # 조기리턴(ealry return)
  temp = f_m(n-1) + f_m(n-2)
  memo[n] = temp
  return temp

# 재귀함수로 리스트 평탄화

def flatten(data):
  output = []
  for item in data:
    if type(item) == list:
      output.extend(flatten(item)) 
      # 재귀 함수 활용으로 다차원 리스트 평탄화
    else:
      output.append(item)
  return output

data = [[1, 2, 3], [4, [5, 6]], 7, [8, 9]]
print(flatten(data)) # [1, 2, 3, 4, 5, 6, 7, 8, 9]