1. 재귀함수(Recursive Function)
알고리즘 문제풀이에서 반복문의 형태로 자주 나타나는 재귀함수는 어떤 함수가 그 함수 안에서 다시 그 함수를 호출하는 방법이다. 함수 입장에서 자가 자신을 다시 호출하는 것을 말한다. 자기 자신을 부르고 또 자기 자신을 부르는 반복형태이기에 while문과 비슷하게 무한루프가 되지 않도록 신경을 써야한다.
재귀 알고리즘은 트리 구조나 그래프 구조를 탐색하기 위한 'DFS(깊이 우선 탐색)' 문제 혹은 메모제이션과 DFS를 활용한 Top-Down '다이나믹 프로그래밍' 문제에서 필수적으로 선행적 이해를 가져야 하는 알고리즘 방법이다.
또한 재귀함수를 이해를 하기 위해서는 선행적으로 이해를 하고 있어야 할 후입선출(Last in First out)구조인 스택(Stack)이 있다. 또한 출력을 할 시, 먼저 혹은 중간 아니면 마지막에 탐색하여 출력할 것인지 선택하는 전위, 중위, 후위 순회구조도 이해해야 한다.
하지만 반복문의 한 형태로써 스택이나 순회구조를 이해하기 전에 이러한 귀납법적 반복문의 형태에 익숙해져야 한다. 닭이 먼저냐 달걀이 먼저냐의 고민과 같이, 선행지식를 알아야 재귀함수를 이해하기 좋은데, 재귀함수를 알아야 선행지식을 이해하기에도 좋다.
그래서 단계적으로 우선 재귀에 익숙해지고 스택의 구조와 순회구조를 이해하여 DFS나 다이나믹 문제를 풀어가겠다.
문제 예시를 통해 재귀함수의 동작 원리를 간단하게 이해하도록 하자.
2. 문제
구구단 2단을 재귀함수로 작성하라.
후위 순회
# 제일 먼저 입력받은 9는 if 조건문을 만족시켜 아래 실행문의 자신의 함수를 다시 호출한다. # 마지막으로 1을 받아 0으로 자신을 호출하고 if 조건문을 만족하지 못하기에 함수는 종료된다. # 제일 마지막에 호출된 것은 'n = 1' 로써 0을 호출한 함수가 종료되었기에 # 다음 실행문 print()문을 실행 후 종료(제일 마지막에 실행된 것이 출력되기에 후위 순회라 한다) def recursive_GuGu(n): if n > 0:# 무한 루프에 빠지지 않도록 n = 0 이 되면 중지하도록 한다. recursive_GuGu(n - 1)# 순차적으로 9를 받아 8로 자신을 다시 호출한다. print('2 * {} = {}'.format(n, 2 * n)) recursive_GuGu(9) 결과: 2 * 1 = 2 2 * 2 = 4 2 * 3 = 6 2 * 4 = 8 2 * 5 = 10 2 * 6 = 12 2 * 7 = 14 2 * 8 = 16 2 * 9 = 18
전위 순회
# 출력문의 순서만 바꿔 전위 순회로 실행하였다. # 제일 먼저 입력된 9가 출력되는 것을 확인할 수 있다. # 그런데 구구단의 순서가 반대로 되어있어 코드를 조금 바꿔야 한다. def recursive_GuGu(n): if n > 0: print('2 * {} = {}'.format(n, 2 * n))# 출력문의 순서가 바뀌었다. recursive_GuGu(n - 1) recursive_GuGu(9) 결과: 2 * 9 = 18 2 * 8 = 16 2 * 7 = 14 2 * 6 = 12 2 * 5 = 10 2 * 4 = 8 2 * 3 = 6 2 * 2 = 4 2 * 1 = 2 ---------- # 제일 먼저 입력된 순서대로 출력되기에 이제는 1부터 입력한다. # 1부터 시작되기에 9에서 시작해서 하나씩 뺀 것과는 반대로 하나씩 더한다. def recursive_GuGu(n): if n < 10:# 10이 호출되면 조건문을 만족하지 못하기에 함수는 종료된다. print('2 * {} = {}'.format(n, 2 * n)) recursive_GuGu(n + 1)# 1씩 '+'를 해준다. recursive_GuGu(1) 결과: 2 * 1 = 2 2 * 2 = 4 2 * 3 = 6 2 * 4 = 8 2 * 5 = 10 2 * 6 = 12 2 * 7 = 14 2 * 8 = 16 2 * 9 = 18
구구단의 전위와 후위 방식의 재귀를 노트에 적어보면서 익숙해지도록 해보자. 앞으로 계속적으로 리스트 자료구조(List)와 스택, 탐색 문제 등에서 지속적으로 재귀함수를 만날 수 있을 것이다.
