[프로그래머스 알고리즘] 4강, 5강: 재귀 알고리즘 (Recursive Algorithm)

재귀 알고리즘 (Recursive Algorithm)

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방법

 

• 재귀 알고리즘은 대부분 iterative version과 recursive version 모두 구현할 수 있다.
• Recursive version은 함수를 호출하는데 드는 시간이 드므로 iterative version이 더 효율적이다. 하지만 사람이 생각하는 방식대로 동작하는 경우가 많아 유용할때도 있다.

 

Ex) Recursive combination 함수 

파스칼의 삼각형 : \( _{n}\mathrm{C}_{m} = _{n-1}\mathrm{C}_{m} + _{n}\mathrm{C}_{m-1} \)

def combi(n, k):
	if (n == k):
    	return 1
    elif (k == 0):
    	return 1
    else:
    	return combi(n-1, k) + combi(n-1, k-1)

 

Ex) Recursive Fibonacci

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

fibo(4) : 9번의 함수 호출이 일어남

함수안에서 2번의 함수 호출이 일어나는데 이중 같은 값을 입력받는 함수 호출도 여러번 일어나므로 효율성이 낮다.

 

 

---

4강 과제 : 피보나치순열

def solution(x):
    if x == 0:
        return 0
    if x == 1:
        return 1
    else:
        return solution(x - 1) + solution(x - 2)

5강 과제 : 재귀적 이진탐색

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)