1. 재귀함수
DFS 구현을 위해 queue 자료구조와 함께 반드시 알아야 하는 함수이다.
파이썬은 디폴트로 재귀함수 호출 제한이 걸려있으므로, 내부적으로 호출제한을 풀어놓는 명령어를 작성해주어야 한다.
- 재귀함수는 일종의 stack 자료구조 형식으로 구현된다.
- 재귀함수를 무한으로 호출하기 위해 시스템적 설정을 해주면 된다.
- 재귀함수를 사용한다면 반드시 탈출조건(return 등 더이상 재귀함수를 호출하지 않는 구문)을 명시해주어야 한다.
def recursion_function(i)
if i == 100
return #탈출조건, 재귀함수가 더이상 호출되지 않으므로 탈출
print('i번째에서 i+1번째 재귀함수를 호출합니다')
recursion_function(i+1)
print('i번째 재귀함수를 종료합니다')위 재귀함수는 1~100번째 재귀함수를 호출합니다를 출력 후 99번째 재귀함수를 종료합니다부터 1번째 재귀함수를 종료합니다까지 출력된다.
즉, stack에 재귀함수가 반복적으로 쌓인 후 return을 통해 재귀함수가 호출되지 않는다면 잔여(하위에 남아있는) 명령구문을 호출 및 실행한다.
또한 일전 stack에 쌓여있으면서 하위 명령구문들을 실행하지 않았을 경우, 하위 명령구문들을 실행하면서 stack이 비어있을때까지 실행후 종료한다.
1-1. 팩토리얼
return을 하면서 재귀함수를 호출한다면, 하위 명령구문들을 남기지 않으므로(모든 재귀함수를 호출한 후 잔여 명령문들이 없어질때까지 반복) 재귀함수가 호출되는 즉시 별도의 실행없이 바로 재귀함수를 종료시킬 수 있다.
def functional_recursive(N):
if N <= 1:
return 1
else:
return N * functional_recursive(N-1)위 재귀함수는 호출 후 잔여 명령문이 없으므로 그대로 종료된다.
1-2. 최대공약수
- case 1 : math.gcd(a,b)
- case 2는 유클리드 호제법(a와 b의 최대공약수는 a와 a//b(나머지)의 최대공약수와 같음을 이용)
def gcd(a,b):
if a%b == 0:
return b
else :
gcd(a, a%b)2. 재귀함수 유의사항
- 재귀함수를 잘 활용한다면 복잡한 알고리즘을 점화식처럼 직관적으로 구성할 수 있다.
- 모든 재귀함수는 반복문을 이용하여 동일하게 구현할 수 있다.
※반복문 보다 재귀함수가 좋다는 의미가 아니라, 상황에 따라 적절하게 사용해야 한다. - 재귀함수를 반복적으로 호출하면 stack 자료구조를 이용하므로, stack 자료구조를 활용하기 위해 역으로 재귀함수를 활용하는 경우도 있다.
