재귀함수

재귀 함수란 자기 자신을 다시 호출하는 함수를 의미

def recursive_function():
  print('재귀 함수 호출')
  recursive_function()

recursive_function()

간단하게 재귀함수를 구현해 보았다.

무한 루프인 재귀함수를 보통 코테에선 사용하지 않으므로 종료조건을 포함한 재귀함수를 사용한다.

def recursive_function(i):
  if i < 100:
    print(i+1, '번째 재귀 함수 호출')
    recursive_function(i+1)
  elif i == 100:
    print('재귀함수 호출 종료')  
    return 
    
recursive_function(1)

팩토리얼 구현 예제

# 반복적으로 구현한 n!
def factorial_iterative(n):
  result = 1
  # 1부터 n까지의 수를 차례대로 곱하기
  for i in range(1, n+1):
    result *= i
  return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):
  if n <= 1: # n이 1이하인 경우 1을 반환
    return 1
  # n! = n * (n-1)!를 그대로 코드로 작성하기
  return n * factorial_recursive(n-1)

# 각각 출력

print('반복구현:', factorial_iterative(5))
print('재귀구현:', factorial_recursive(5))

반복문을 사용하지 않고 수학적인 공식을 이용해 구현한 것이 재귀 구현이다.

최대 공약수 계산 예제

유클리드 호제법을 코드로 구현한다면

def gcd(a,b) :
  if a % b == 0:
    return  b
  else : 
    return gcd(b, a%b)

print(gcd(192,162))

이와 같이 재귀함수를 잘 활용하면 복잡한 알고리즘도 수학적 공식을 이용해 간결하게 작성할 수 있다

단, 오히려 다른사람이 이해하기 어려운 수도 있다(공식을 모르면)

컴퓨터가 함수를 연속적으로 호출하면 메모리 내부에 스택 프레임에 쌓인다. 그래서 스택을 사용해야 할때 스택라이브러리 대신 재귀함수를 이용하는 경우도 많다(BFS)