[알고리즘 강의] 파트5. 재귀 알고리즘(Recursive Algorithms) 응용

재귀함수란?

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것

조합의 수 계산하기

문제) n개의 서로 다른 원소에서 m개를 택하는 경우의 수
정답) nCm=n! / (m!(n-m)!)

 

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

조합의 수 계산 - 재귀적 방법

nCm = n-1Cm + n-1Cm-1
-> 특정한 하나의 원소 입장에서 볼 때, 이 원소를 포함하는 경우와 그렇지 않은 경우를 따로 계산해서 더한다.

 

#올바르지 않은 구현
def combi(n,m):
  return combi(n-1,m) + combi(n-1,m-1) # Trivial case를 고려하지 않은 실수!


#올바른 구현
def combi(n,m):
  if n==m:
    return 1
  elif m==0:
    return 1
  else:
    return combi(n-1,m)+combi(n-1,m-1)

단, 효율성 측면에선 좋지 않음

재귀 알고리즘의 유용성

문제: 하노이의 탑

 

실습코드 - 재귀적 이진 탐색 구현

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)

 

* 프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?' 강의를 듣고 정리하였습니다.