재귀 함수(Recursive Functions)란?
하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
재귀함수를 이용하는 이유 : 생각보다 많은 종류의 문제가 재귀적으로 해결 가능함
예를 들면, 이진트리에서
왼쪽 서브트리의 원소들은 모두 작거나 같다
오른쪽 서브트리의 원소들은 모드 클 것
이 원칙을 모든 노드에 대해서 적용해야한다.
보다 간단한 예로, 자연수의 합 구하기가 있다.
문제 : 1부터 n까지 모든 자연수의 합을 구하시오
def sum(n):
if n <= 1:
return n
else:
return n + sum(n-1)
n = 10
print(sum(n))
재귀 함수를 호출 할 때는 종결 조건이 매우 중요함.
모든 재귀 알고리즘은 이와 대칭되는 반복 순환되는 형태를 가지는 반복 버전(iterative version)을 갖는다.
# Recursive viersion
def sum(n):
if n <= 1:
return n
else:
return n + sum(n-1)
# Iterative version
def sum(n):
s = 0
while n >= 0:
s += n
n -= 1
return s
효율성을 비교하면 n이 증가할 수록 재귀 알고리즘은 n번의 횟수만큼 호출하는 횟수가 증가하는 O(n)의 시간복잡도를 갖고 반복 버전또한 n의 비례하는 O(n)복잡도를 갖게 된다.
하지만 재귀 알고리즘은 함수를 호출하고 반환하는 부가적인 작업이 필요하므로 효율은 반복버전보다 낮다.
재귀 알고리즘 추가 예제
def factorial(n):
if n <= 1:
return 1
else:
return n * factorial(n-1)
연습 문제
Fibonacci 순열 구현해보기
# recursive version
def fibo(x):
if x == 0:
return 0
elif x == 1:
return 1
else:
return fibo(x-1) + fibo(x-2)
# iterable version
def solution(x):
result = [0, 1]
if x == 0:
return result[0]
elif x == 1:
return result[1]
else:
for i in range(2,x+1):
result.append(result[i-1]+result[i-2])
return result[-1]
Comments