조합의 수 계산

• n개의 서로 다른 원소에서 m개를 택하는 경우의 수 구하기

• 일반적인 방법
  

• 재귀적 방법
  

• trivial case를 고려해야함
  

하노이의 탑

• 크기 순서로 쌓여 있는 원반을 한 막대에서 다른 막대로 옮기기
• 더 큰원반 작은 원반 위에 올릴 수 없음

피보나치 순열

재귀적(recursive) vs 반복적(iterative) 방법 비교

# 재귀적(recursive) 방법
import time

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

# 반복적(iterative) 방법
def iter(n):
	if n <= 1:
    		return n
    	else:
        	i = 2
            	t0 = 0
                t1 = 1
                while i <= n:
                	t0, t1 = t1, t0 + t1
                    	i += 1
        return t1
        
 
 while True:
 	nbr = int(input("Enter a number: "))
    	if nbr == -1:
    		break

	ts = time.time()
    	fibo = iter(nbr)
	ts = time.time() - ts
	print("Iterative version: %d (%.3f)" %(fibo, ts))
	ts = time.time()
	fibo = rec(nbr)
	ts = time.time() - ts
	print("Recursive version: %d (%.3f)" %(fibo, ts))

실행 결과

python3 recursive_iterative_compare.py
Enter a number: 30
Iterative version: 832040 (0.000)
Recursive version: 832040 (0.287)
Enter a number: 35
Iterative version: 9227465 (0.000)
Recursive version: 9227465 (3.295)
Enter a number: 40
Iterative version: 102334155 (0.000)
Recursive version: 102334155 (36.201)

• 재귀적 방법이 훨신 더 걸린다

[실습] 재귀적 이진탐색

참고

문제

어서와! 자료구조와 알고리즘은 처음이지? 5강 실습: 재귀적 이진탐색

문제 설명

리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어지고, 또한 탐색의 대상이 되는 리스트 내에서의 범위 인덱스가 l 부터 u 까지로 (인자로) 정해질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.

인덱스 범위를 나타내는 l 과 u 가 인자로 주어지는 이유는, 이 함수를 재귀적인 방법으로 구현하기 위함입니다. 빈 칸에 알맞은 내용을 채워서 재귀 함수인 solution() 을 완성하세요.

예를 들어,L = [2, 3, 5, 6, 9, 11, 15]x = 6l = 0u = 6의 인자들이 주어지면, L[3] == 6 이므로 3 을 리턴해야 합니다.

또 다른 예로,L = [2, 5, 7, 9, 11]x = 4l = 0u = 4로 주어지면, 리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴해야 합니다.

---

나의 풀이

• 빈칸채우기 문제
• 재귀호출한다는 것이 포인트!

solution.py

def solution(L, x, l, u):
    if l > u:             # lower가 upper보다 크면 List길이는 0
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return solution(L, x, l, mid -1) # 가존upper값은 mid기준으로 다음값은 무의미

    else:
        return solution(L, x, mid+1, u) # 기존lower값은 mid기준으로 그전값은 무의미