자료구조(2) - 재귀 함수

 

<개념>

재귀 : 자기 자신을 의미 Ex) 재귀대명사( himself - 그자신)

위의 뜻처럼 함수 내부에서 본인의 함수를 호출하는 함수를 재귀함수라 한다.

가장 자주 나오는 예시로는 Factorial(팩토리얼) 이 있다. 

Factorial의 의미는 해당 주어진 숫자부터 1까지의 곱을 의미한다

표기 !로 한다. 

# 정의
N! = N x (N-1) x . . . x 3 x 2 x 1

#Example 
5! = 5 x 4 x 3 x 2 x 1                             
7! = 7 x 6 x 5 x 4 x 3 x 4 x 3 x 2 x 1

 

 

<구현>

해당 알고리즘을 단순히 구현하자면 다음과 같이 구현할 수 있다.

def Factorial_simple(n):    # Factorial - 단순버전
    result = 1              # 결과값 지정
    for i in range(1, n+1): # range(n)이면 i=0부터 시작이라 결과값이 0이됨
        result *= i

    return result

하지만 이방법 말고도 재귀함수를 이용한 방법이 있는데 

def factorial(n):                # factorial 함수
    if n == 1:			# 탈출 조건
        return 1			
    return n * factorial(n-1)     # 본인의 함수 호출

해당 방법이 재귀함수를 이용한 방법으로 함수를 끝내기 전에 자기 함수를 다시 호출하는 모습을 보인다. 

 

작동과정을 그림으로 표현하자면 

 

Factorial 작동과정

대략적으로 이럴 것이다. 당연히 return하는 순서대로 값이 업데이트가 된다.

재귀함수가 사용될 조건으로는 계속해서 동일한 반복이 필요한 함수나 수열의 점화식, 피보나치 수열 등을 이용할 때 좋다. 이외에도 모든 경우의 수를 파악할 때도 유용하다. ( 이후에 하나씩 구현한 코드를 넣어볼 예정 )

---