재귀 알고리즘

재귀 알고리즘 기초

재귀 : recursion

• 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우

• 무한히 존재하는 자연수를 재귀적 정의를 사용하여 두 문장으로 정의

  • 1은 자연수
  • 어떤 자연수의 바로 다음 수도 자연수

• 재귀를 효과적으로 사용하면 이러한 정의 뿐만 아니라 프로그램을 간결하고 효율성 좋게 작성할 수 있음

  팩토리얼 factorial

  양의 정수의 곱을 구하는 문제
  양의 정수를 순서대로 곱한다는 의미로 순차 곱셈이라고도 함
  재귀를 사용하는 대표적인 예

  양의 정수 n의 팩토리얼(n!)의 재귀적 정의

  def factorial(n: int) -> int:
     if n > 0:
         return n * factorial(n-1)
     else:
         return 1
  if __name__ == '__main__':
     n = int(input('출력할 팩토리얼값을 입력하세요 : '))
     print(f'{n}의 팩토리얼은 {factorial(n)}입니다.')
  

  n 이 5일 경우 :

  5*(factorial(5-1)) => 5*(factorial(4))

  5*4*(factorial(4-1)) => 5*4*(factorial(3))

  5*4*3*(factorial(3-1)) => 5*4*3*(factorial(2))

  5*4*3*2*(factorial(2-1)) => 5*4*3*2*(factorial(1))

  5*4*3*2*1

  120

  직접재귀 와 간접재귀

• 직접재귀 (direct) : 자신과 똑같은 함수를 호출하는 방식

• 간접재귀 (indirect) : a() 함수가 b() 함수를 호출하고 다시 b() 함수가 a() 함수를 호출하는 구조

  직접재귀 )
  a () => a()
  간접재귀 )
  a() => b() => a()