[Python][이코테] 재귀함수/팩토리얼재귀

재귀함수

 

자기 자신을 호출하는 함수이다.

 

말이 어렵다 직접 코드로 보자

 

# 5-3 DFS,BFS 재귀 함수

def recursive_function():
    print("재귀 함수를 호출합니다.")
    recursive_function()
    
recursive_function()

#RecursionError: maximum recursion depth exceeded while calling a Python object

recursive_function() 함수 안에서 recursive_function() 함수를 호출한다.

 

뭐 이런 거다.

 

함수가 함수 본인을 호출하여 다시 함수를 실행하는 것이다. 이후 해당 함수가 종료되면 가장 마지막으로 종료된 시점의 함수의 다음 행부터 명령어를 시작한다.

 

하지만 위의 코드를 실행시키면

 

RecursionError: maximum recursion depth exceeded while calling a Python object

위와 같은 에러가 나오게 되는데

 

이유는 recursive_function() 함수를 계속해서 호출하다 보니 재귀의 최대 깊이를 초과했다는 말이다.

즉 재귀함수를 무한대로 반복시킬 수 없다.

 

그래서 재귀함수는 while True: 반복문처럼 종료 시점이 반드시 필요하다.

 

---

 

# 5-4 DFS,BFS 재귀 함수 종료 조건

def rec(i):
    if i == 100:
        print("종료")
        return
    rec(i+1)
    print(i, "번째에서 종료")
    
rec(0)

위의 코드를 실행시키면

결과 창은

종료
99 번째에서 종료
98 번째에서 종료
97 번째에서 종료
...
1 번째에서 종료

이런 식으로 나오게 된다.

 

즉 rec() 함수를 100번 반복하고 100번째에서 종료를 출력 후

 

100번째의 마지막인 99번째 재귀 때로 돌아가서 '99 번째에서 종료'를 실행하고

 

다시 그 마지막 재귀로 돌아가서 '98 번째에서 종료'를 실행하는 식으로

 

즉 스택 자료구조를 이용한다.

 

스택 자료구조를 이용해야 하는 알고리즘은 재귀함수를 이용하여 간편하게 구현할 수 있으며 이는 추후에 배울 DFS에 사용된다.

 

# --- 책의 코드 ---
def recursive_function(i):
    if i == 100:
        return
    print(i, '번째 재귀함수에서 ', i+1, '번째 재귀 함수를 호출합니다.')
    recursive_function(i+1)
    print(i, '번째 재귀 함수를 종료합니다.')
    
recursive_function(1)

위는 저자가 작성한 책의 코드이므로

 

만약 재귀함수가 잘 이해가 되지 않는다면

 

위의 코드를 실행한 후 결과창을 보면 이해가 될 것이다.

 

---

팩토리얼 값 구하기

팩토리얼 계산은 재귀함수로 풀 수 있는 가장 대표적인 방법이다.

 

팩토리얼은 5! = 5 * 4 * 3 * 2 * 1

 

처럼 '숫자'! 가 붙으면

 

해당 숫자부터 1까지의 모든 자연수를 곱한 것이 값이 된다.

 

5! = 120 이 되는 것이다.

 

# 5-5 DFS,BFS 팩토리얼
#재귀 미사용
def normal(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

print(normal(5))


# 재귀 사용
def facto(n):
    if n == 1:
        return 1
    return n * facto(n-1)

print(facto(5))

위는 재귀를 사용하지 않고 반복문으로 해결한 방법

 

밑은 재귀함수를 사용한 방법이다.