- 재귀(Recursion)란?
- 재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다.
- 재귀 함수는 위의 로직대로 자기 자신을 다시 호출하는 형태를 갖게 되는데 조건을 정해주지 않으면 최대 재귀 깊이 초과 오류(
Recursion Error)가 발생한다.- Python 기준 최대 재귀 깊이는 1000이다. 기본 재귀 깊이의 제한이 매우 적기 때문에
sys를 사용해서sys.setrecursionlimit(10 ** 6)을 작성해 임의로 재귀의 최대 깊이를 설정할 수 있다.
- 재귀 함수는 위에서 보는 것과 같이 내부적으로 스택 자료구조와 동일하다.
- Python에서
return이 의미하는 바는 무엇인가?함수를 실행했던 위치로 돌아가라, 함수를 여기서 끝내라return,return None,return을 사용하지 않는 경우3가지로 구분할 수 있다.
ⅰ)
return인 경우
- early return의 경우 많이 사용된다. 전부 다 돌지 않고 어떤 시점에서 실행을 중단하느냐에 대한 의미로 사용이 된다고 생각하면 된다.
ⅱ)
return None인 경우
- 원하는 경우가 아닌 경우 None을 리턴한다.
ⅲ)
return을 사용하지 않은 경우
- 무언가를 반환하는 함수가 아닌 단순 연산의 함수 경우를 말한다.
- 연산이 끝난 후 보통
True나False를 리턴하는 함수가 대부분이지만 이 경우가 아니라 단순히 global 변수의 연산이 목적인 경우 사용하지 않는 경우도 있다.
- 팩토리얼 재귀함수 코드
def factorial(n):
if n > 0:
n * factorial(n-1)
else:
return 1
factorial()함수로 3의 팩토리얼 값을 구하는 과정을 정리해보자.①. 함수 호출식
factorial(3)을 실행하면factorial()함수가 호출된다. 이 함수는 3을 전달받아3 × factorial(2)의 값을 반환한다. 실제 인수로 2를 전달해서 함수factorial(2)를 호출한다.②. 호출된
factorial()함수는 2를 전달받아2 × factorial(1)의 값을 반환한다. 실제 인수로 1을 전달해서 함수factorial(1)을 호출한다.③. 호출된
factorial()함수는 1을 전달받아1 × factorial(0)의 값을 반환한다. 실제 인수로 0을 전달해서 함수factorial(0)을 호출한다.④.
factorial(0)은 1이다. 1 × 1 = 1이므로 1을 리턴한다.⑤. 1을 전달받은
factorial()함수는2 × factorial(1)을 반환한다.⑥. 2를 전달받은
factorial()함수는3 × factorial(2)을 반환한다.
- 팩토리얼 코드 실행 과정을 설명한 그림이 위의 스택 이미지가 된다.
- 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해줘야 한다. 종료 조건을 명시하지 않으면 함수가 무한 호출되어
RecursionError가 출력될 수 있기 때문이다.
- 재귀 알고리즘 관련 문항 정리
🐢