[알고리즘] 재귀 함수 (Recursive Function) - Python

재귀함수란?

자기 자신을 호출하는 함수로 팩토리얼 하노이 탑 등 동일한 작업을 반복해서 수행하는 문제엣 많이 사용됨.

 

 

재귀함수의 장점

• 직관적인 모습으로 간단히 구현가능
• DFS, 백트래킹, 그리디 등 많은 알고리즘에서 사용되어 꼭 알아두어야 할 개념

 

재귀함수의 단점

• 종료 조건을 명시해주지 않으면 무한루프에 빠질 수 있음.
• 깊이가 너무 깊어지면 ( 너무 많은 반복호출 ) 많은 메모리를 차지한다.
• 불필요한 연산을 할 가능성이 있음.

 

Python 에서의 재귀

파이썬에서 재귀의 깊이는 1000회라는 제한이 있다.

def hello():
    print('Hello, world!')
    hello()
 
hello()

그래서 위 코드를 실행시키면 

Hello world! 라는 문자열이 계속 출력되다 에러가 발생한다.

위에서 말한 1000회의 깊이를 초과한 그 순간 발새하는 에러이다. - maximum recursion depth

즉, hello 함수가 자기자신을 계속 호출하다가 최대 재귀 깊이를 초과하면 RecursionError가 발생한다.

 

그렇기 때문에 꼭 종료 조건을 만들어줘야한다.

 

하지만 이러한 재귀 깊이 제한을 재설정하는 방법이 있다.

import sys
sys.setrecursionlimit(100000)

위 코드를 상단에 작성하면 재귀의 깊이가 최대 100000으로 바뀌게 된다.

100000은 본인이 풀 문제에 따라 알맞게 설정이 가능하다.

 

그래서 혹시라도 모르니 DFS 등 과 같이 재귀를 사용하는 문제는

위 코드로 최대 깊이를 재설정 해주고 시작하는 것이 좋다!.