프로그래머스_강의5

재귀적 알고리즘 - 응용 (Recursive Algorithms)

재귀함수(recursive functions)란?

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

1) 조합의 수 계산
문제 : n개의 서로 다른 원소에서 m개를 택하는 경우의 수

def combi(n,m) :
  if n == m :
      return 1
  elf m == 0 :
      return 1
  else :
      return combi(n-1,m) + combi(n-1,m-1)

===> 효율성 측면에서 과연 좋을까???

2) 문제 : 하노이의 탑
3) 피보나치 수열의 재귀알고리즘에대한 효율
fibo(4) = fibo(3) + fibo(2)
에서 fibo(2)가 두번, fibo(1)도 세번, 계속해서 한번만 구해서 그 값을 쓰지 않고 계속해서 값을 구해야한다.
===> 도합 9번의 함수 호출을 가져온다.
====> 성능저하 발생
4) 연습문제
<재귀적 이진탐색>

다른 사람의 풀이를 확인해본 결과 맨 윗줄칸에 l > u 일 경우에도 return -1값이 잘 나오는 것을 알 수있다. 값을 굳이 비교하지 않아도 리스트가 비어있는 경우를 확인할 수 있다.