[python] 재귀 함수

Soy·2023년 9월 13일

재귀 함수

반복문으로 팩토리얼 구하기

def factorial(n):
  output = 1

  for i in range(1, n+1):
    output *= i

  return output

print("1!:", factorial(1))
print("2!:", factorial(2))
print("3!:", factorial(3))
print("4!:", factorial(4))
print("5!:", factorial(5))

- 실행 결과
1!: 1
2!: 2
3!: 6
4!: 24
5!: 120

재귀 함수로 팩토리얼 구하기

def factorial(n):
  if n == 0:
    return 1
  else:
    return n * factorial(n-1)

print("1!:", factorial(1))
print("2!:", factorial(2))
print("3!:", factorial(3))
print("4!:", factorial(4))
print("5!:", factorial(5))

- 실행 결과
1!: 1
2!: 2
3!: 6
4!: 24
5!: 120

재귀 함수의 문제

상황에 따라 같은 것을 기하급수적으로 많이 반복할 수 있다. (= 코드 실행 시간이 굉장히 오래 걸릴 수 있다.)
→ 메모화(memoization)으로 해결.
피보나치 수열

# 피보나치 수열 기본
def fibonacci(n):
  if n == 1:
    return 1
  if n == 2:
    return 1
  else:
    return fibonacci(n-1) + fibonacci(n-2)

print("fibonacci(1):", fibonacci(1))
print("fibonacci(2):", fibonacci(2))
print("fibonacci(3):", fibonacci(3))
print("fibonacci(4):", fibonacci(4))
print("fibonacci(5):", fibonacci(5))

- 실행 결과
fibonacci(1): 1
fibonacci(2): 1
fibonacci(3): 2
fibonacci(4): 3
fibonacci(5): 5

# 피보나치 수열 연산 횟수
counter = 0

def fibonacci(n):
  print("fibonacci({})를 구합니다.".format(n))
  global counter
  counter += 1

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

fibonacci(10)
print("fibonacci(10) 계산에 활용된 덧셈 횟수는 {}번 입니다.".format(counter))

- 실행 결과
fibonacci(10)를 구합니다.
fibonacci(9)를 구합니다.
fibonacci(8)를 구합니다.
fibonacci(7)를 구합니다.
...
fibonacci(1)를 구합니다.
fibonacci(2)를 구합니다.
fibonacci(10) 계산에 활용된 덧셈 횟수는 109번 입니다.

(재귀 함수는 처음부터 다시 계산하기 때문에 계산 횟수가 기하급수적으로 늘어나 연산 시간이 오래 걸린다.)

global 키워드

global 변수 이름

파이썬은 함수 내부에서 함수 외부에 있는 변수를 참조(reference)하지 못한다.
그래서 아래 코드처럼 fibonacci 함수 내에서 global 키워드를 지우고 실행한다면 UnboundLocalError가 발생한다.

# 피보나치 수열 연산 횟수
counter = 0

def fibonacci(n):
  print("fibonacci({})를 구합니다.".format(n))
#  global counter
  counter += 1

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

fibonacci(10)
print("fibonacci(10) 계산에 활용된 덧셈 횟수는 {}번 입니다.".format(counter))

메모화

재귀 함수는 같은 값을 구하는 연산을 반복하기 때문에 같은 값을 한 번만 계산하도록 메모화를 사용하면 효율적으로 재귀 함수를 사용할 수 있다.
dictionary에 한 번 계산한 값을 저장(=메모(memo))한다.
예시

dictionary = {
    1: 1, 
    2: 1
}

def fibonacci(n):
  if n in dictionary:
    return dictionary[n]
  else:
    output = fibonacci(n-1) + fibonacci(n-2)
    dictionary[n] = output
    return output

print("fibonacci(10):", fibonacci(10))
print("fibonacci(20):", fibonacci(20))
print("fibonacci(30):", fibonacci(30))
print("fibonacci(40):", fibonacci(40))
print("fibonacci(50):", fibonacci(50))

- 실행 결과
fibonacci(10): 55
fibonacci(20): 6765
fibonacci(30): 832040
fibonacci(40): 102334155
fibonacci(50): 12586269025

조기 리턴

아래와 같이 흐름 중간에 return 키워드를 사용하여 조기 리턴(early return)을 하면 들여쓰기 단계가 줄어 코드를 더 쉽게 읽을 수 있다.

# 일반적인 return
def fibonacci(n):
  if n in dictionary:
    return dictionary[n]
  else:
    output = fibonacci(n-1) + fibonacci(n-2)
    dictionary[n] = output
    return output

# early return
dictionary = {
    1: 1, 
    2: 1
}

def fibonacci(n):
  if n in dictionary:
    return dictionary[n]

  output = fibonacci(n-1) + fibonacci(n-2)
  dictionary[n] = output
  return output

리스트를 평탄화하는 재귀 함수 만들기

def flatten(data):
  output = []

  for i in data:
    if type(i) == list:
      output += flatten(i)      
    else:
      output.append(i)

  return output