[python]재귀함수(Recursive Function)

함수

관련내용

함수(Function): 함수의 정의
• 전역변수와 지역변수
• 함수: 인수의 전달
• 가변인수
• 발생자(generator)
• 주요한 내장함수들
• 재귀함수(Recursive Function)
• 람다함수(Lambda Function)
• Python의 함수는 1급(First Class)객체
• 1급 객체와 변수의 영역
• 클로저(Closure)
• 데코레이터(Decorator, 장식자)

재귀함수(Recursive Function)

함수는 다른 함수를 포함할 수 있습니다. 그 포함된 함수가 함수 자신일 경우 재귀함수(Recursive Function)라고 합니다. 예를 들어 식 1과 같이 1부터 지정된 수까지 모든 정수를 곱하는 경우 즉, factorial을 재귀함수로 작성할 수 있습니다.

n factorial = n! = 1·2·3 … n

(식 1)

def factorial(x): 
    if x==1: 
        return 1 
    else: 
        return (x*factorial(x-1))

factorial(5)

120

위 사용자 정의 함수 factorial()은 if ~ else 구문을 적용하였으며 if와 else 블럭 모두 return() 함수를 하위 문으로 가지고 있으므로 어떤 블럭이 실행되더라도 함수는 종결됩니다. 그러나 else 블럭의 실행은 함수 자신을 반환하는 것으로 if 블럭이 실행되지 않는 이상 함수의 실행이 반복됩니다. 최종적으로 else 문의 실행으로 1을 반환하는 경우 x == 1이 되어 실행이 종결됩니다. 이같은 종결조건은 재귀함수의 필수 요소입니다.

위 함수에 인수 5를 전달하여 실행하는 과정은 다음과 같습니다.

factorial(5)	(5) 전달된 인수
→ 5 × factorial(4)	fatorial(4) 호출
→ 5 × 4 × factorial(3)	fatorial(3) 호출
→ 5 × 4 × 3 × factorial(2)	fatorial(3) 호출
→ 5 × 4 × 3 × 2 × factorial(1)	fatorial(2) 호출
→ 5 × 4 × 3 × 2 × 1	(1) 호출, 실행종결

다음은 내장함수인 str()와 list()를 적용하여 인수로 전달한 수를 각 자리의 숫자로 분리한 것입니다.

• str(x)
  • x를 문자열로 형변환하는 내장함수
  • x는 수치형 리터럴 또는 컬렉션 등의 모든 자료형
• list(x)
  • 객체 x를 list 형으로 변환하는 함수
  • 전달하는 인수가 없는 경우 빈 리스트를 생성

list(str(98))

['9', '8']

재귀함수를 사용하여 위 결과를 나타내 봅니다.

def eachNum(x): 
    if x < 10: 
        print(x, end=" ") 
    else: 
        eachNum(int(x/10)) 
        print(x%10, end=" ")

eachNum(98)

9 8 

위 함수의 실행과정은 그림 1과 같이 나타낼 수 있습니다.

그림 1. 재귀함수 exchNum()의 실행과정.

eachNum(89234)

8 9 2 3 4 

재귀함수는 동일한 함수를 반복 실행하게 합니다. 그러므로 복잡한 코드를 간단히 만들 수 있지만 함수 자체가 복잡하면 가독성이 저하되고 속도면에서 불리해집니다. 다음은 피보나치 수열을 나타내기 위해 재귀적 사용 여부에 따라 작성된 두 개의 함수들에 대한 실행시간을 살펴봅니다. 피보나치 수열은 식 2와 같이 계산됩니다.

피보나치 수열 :	0, 1, 1, 2, 3, 5, 8, 13, …	(식 2)
an	= an-1 + an-2

함수 fib(n)은 재귀함수입니다. 이 함수의 실행 시간을 측정하기 위해 파이썬 패키지 time의 time() 함수를 사용합니다.

• time.time()
  • time 모듈 함수
  • 함수가 실행되는 시간을 초 단위로 반환

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

from time import time

st=time()
re=[]
for i in range(31):
    re.append(fib(i))
print(re)
et=time()
print(f"실행시간:{et-st}")

[0, 1, …, 514229, 832040]
실행시간:0.7545561790466309

다음 함수는 피보나치 수열의 일반식을 기반으로 작성한 것으로 재귀함수보다 복잡한 구조를 가집니다. 그러나 함수는 위 재귀함수와 비교하여 매우 빠른 실행을 나타냅니다. 즉, 재귀함수의 경우 메모리 관리 측면에서 비효율적입니다.

def fib2(n):
    re=[0]*(n+1)
    if n>0:
        re[1]=1
        for i in range(2, n+1):
            re[i]=re[i-1]+re[i-2]
    return(re)

st=time()
print(fib2(30))
et=time()
print(f"실행시간:{et-st}")

[0, 1, …, 514229, 832040]
실행시간:0.001049041748046875