재귀함수란?

재귀함수는 함수 내부에서 자기 자신을 호출하여 문제를 해결하는 방법입니다.

예를 들어, 피보나치 수열을 구하는 함수를 작성한다면, 이 함수 내부에서 자기 자신을 호출하여 피보나치 수열을 계산합니다.

재귀함수는 반복문과 같은 역할을 할 수 있지만, 구현이 비교적 간단하고 명확한 경우가 있습니다.

종료조건을 제대로 명시하지 않으면 무한히 호출되기에 반드시 종료 조건을 명시 해야 한다.

재귀함수의 예시

아래는 재귀함수의 대표적인 예시들입니다.

• 팩토리얼 구하기

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

• 피보나치 수열 구하기

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

• 이진 탐색하기

  def binary_search(arr, target, low, high):
      if low > high:
          return -1
      mid = (low + high) // 2
      if arr[mid] == target:
          return mid
      elif arr[mid] > target:
          return binary_search(arr, target, low, mid-1)
      else:
          return binary_search(arr, target, mid+1, high)