재귀적 방법은 사람의 생각을 알고리즘으로 옮기기 직관적이지만 반복적 방법에 비해 효율성이 떨어질 수 있다.

예) 조합의 수 계산 - n개의 서로 다른 원소에서 m개를 택하는 경우의 수

n! / m! * (n-m)!

from mathimport factorialas f

defcombi(n, m):
	return f(n) / (f(m) * (f(n-m))

n개의 서로 다른 원소에서 m개를 택하는 경우의 수는 n-1개에서 m개를 택하는 경우와 n-1개에서 m-1개를 택하는 경우를 더한 것과 같다.

특정한 하나의 원소 입장에서 n-1개에서 m-1 경우의 원소를 포함하는 경우와 그렇지 않은 경우를 따로 계산해서 더한다.

defcombi(n, m):
	if n == m:
		return 1
	elif m == 0:
		return 1
	else:
		return combi(n-1, m) + combi(n-1, m-1)

재귀 알고리즘이 유용할 때

문제) 하노이의 탑 - 반복문으로 풀려면 꽤 어렵다

재귀 알고리즘의 효율

재귀가 비효율적인 이유는 같은 함수를 여러번 계산하는 것이 크다.

fibo(4) = fibo(3) + fibo(2) = fibo(2) + fibo(1) + fibo(1) + fibo(0) = fibo(1) + fibo(0) + fibo(1) + fibo(1) + fibo(0)

연습 - 재귀적 이진 탐색

defbinsearch(L, x, lower, upper):
	if ____:
		return -1
	mid = (lower + upper) // 2
	if x == L[mid]:
		return mid
	elif x < L[mid]:
		return ____
	else:
		return ____

defbinsearch(L, x, lower, upper):
	mid = (lower + upper) // 2
	if lower > upper:
		return -1
  print(lower, mid, upper)
	if x == L[mid]:
		return mid
	elif x < L[mid]:
		return binsearch(L, x, lower, mid - 1)
	else:
		return binsearch(L, x, mid + 1, upper)
	
L = [1, 3, 7, 9, 13, 14, 16, 17, 19, 25, 33, 53, 79, 100, 123]
x = int(input("Target Number: "))
print(binsearch(L, x, 0, len(L) - 1))