Python 재귀 알고리즘(Recursive Algorithms)

재귀 알고리즘(Recursive Algorithms)

재귀함수(recursive functions)란?

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

간단한 예제: n이 입력될 때 1부터 n까지의 합

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

재귀 알고리즘의 효율

1. Iterative version

효율성: O(n)

def sum(n):
   s = 0
   while n >= 0:
       s += n
       n -= 1
   return s

2. Recursive version

효율성: O(n)

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

피보나치 수열

1. Interative version

def solution(x):
    a, b = 0, 1
    for i in range(x):
        a, b = b, a+b
    return a

2. Recursive version

solution(4) = solution(3) + solution(2) 에서 solution(3)과 solution(2)를 구하기 위해서 함수를 여러번 호출해야하고 중복되는 값을 계속해서 구한다.

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

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

문제: n개의 서로 다른 원소에서 m개를 선택하는 경우의 수

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

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)

효율성 측면에서 보면 n이 커지면 함수가 많이 호출되 않좋다. 수를 곱하는 반복문을 사용하는것이 효율성에 더 좋다.

재귀로 구현한 이진탐색

리스트 L 과 찾으려는 원소 x, 그리고 리스트의 범위 l부터 u까지가 주어졌을때

범위 l, u를 주는 이유는 재귀적인 방법으로 구현하기 위해서

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)