def solution(L, x, l, u):
    if:
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        returnelse:
        return

1. 기초

• 개요

재귀함수 recursive functions 란?

: ㈛나의 함수에서 자신을 다시 호출㈛여 작업을 수행㈛는 것 (알고리즘의 성질)

• 생각보다 많은 종류의 문제가 재귀적으로 해결 가능

• ex. 이진 트리 binary trees

  

  • 노드12를 기준으로 왼쪽 서브트리의 원소9들은 모두 작거나 같을 것
  • 오른쪽 서브트리의 원소17들은 모두 클 것
  • → 이 원칙을 모든 노드에 대해서 적용
  • ex. 10을 찾아라 ! → 재귀적인 방법으로 ㄱㄴ (12 → 9 → 10)

• ex. 1부터 n까지 모든 자연수의 합을 구하시오.

  • $S = \Sigma^n_{k=1} k = n + \Sigma^{n-1}_{k=1} k$
  • def sum(n): return n + sum(n-1

• ⭐ 종결 조건이 매우 중요 !

  

• 재귀 알고리즘의 효율

  

  • 반복 알고리즘보단 효율성 떨어짐
  • n*(n+1)/2 → O(1) !!

• 재귀 알고리즘 추가 예제 $n!$

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

• 연습 문제 Fibonacci 순열

  

  # 재귀적 방법
  def solution(x):
      answer = 0
      if x<=1:
          return x
      else:
          answer = solution(x-2) + solution(x-1)
      return answer
  
  # 반복적 방법
  def solution(x):
      if n<=1: return n
  		else:
  				i = 2
          t0 = 0
  				t1 = 1
  				while i <= n:
  					t0, t1 = t1, t0 + t1
  				return t1
  

2. 응용

• 개요

• 재귀적 알고리즘 : 효율성 부분에서는 반복적 방법보다 약점,,

• ex. n개의 서로 다른 우너소에서 m개를 택하는 경우의 수

  

  • 수학적 방법

    • from math import factorial as f def combi(n, m): return f(n) / (f(m) * f(n-m))

  • 재귀적 방법

    

    • def combi(n, m): return combi(n-1, m) + combi(n-1, m-1)

      • → trivial case를 고려하지 않는 실수! (재귀 알고리즘 할 때 가장 실수㈛기 쉬운 부분)

        

        비효율적 !!!!!

• 재귀 알고리즘의 유용성 (효율이 떨어지더라도 왜 재귀 알고리즘?)

  • ex. 하노이의 탑

    

    • 큰 원반 → 작은 원반 순으로 쌓아야 한다는 규칙 있을 때
    • 이런 경우, 재귀가 반복보다 쉬움!

• 재귀 알고리즘의 효율

  • 피보나치 재귀 알고리즘의 비효율성 (재귀 < 반복👍)

    

• [연습 문제] 재귀적 이진 탐색

  def solution(L, x, l, u):
      if **l>u**:
          return -1
      mid = (l + u) // 2
      if x == L[mid]:
          return mid
      elif x < L[mid]:
          return **solution(L, x, l, mid-1)**
      else:
          return **solution(L, x, mid+1, u)**