[코딩테스트/Python] 꼭 필요한 자료구조 기초: 재귀함수

스택과 큐 관련 내용은 이전 글 참고

https://emperor-one-data-study.tistory.com/33

[코딩테스트/Python] 꼭 필요한 자료구조 기초: 스택과 큐

 

DFS와 BFS를 구현하기 위해서는 스택과 큐 뿐만 아니라 재귀 함수에 대해서도 이해하고 있어야 한다. 

 

재귀 함수 (Recursive Function)

: 자기 자신을 다시 호출하는 함수 

 

가장 간단한 재귀함수 예제

위와 같이 재귀 함수 호출 문구가 무한히 호출된다. 자기 자신을 무한히 불러오기 때문이다. 

RecursionError: maximum recursion depth exceeded while calling a Python object

다음과 같은 내용이 출력되는데, 파이썬 인터프리터가 호출할 수 있는 호출 횟수를 넘어갔기 때문에 발생하는 에러이다. 따라서 재귀 호출을 무한대로 진행할 수는 없다. 

 

재귀 함수의 종료 조건

재귀 함수를 문제 풀이에 사용할 때는 꼭 종료 조건을 명시해야 한다. 조건을 명시하지 않으면 위의 결과처럼 함수가 무한 호출된다. 

다음은 재귀함수를 100번 호출하도록 하는 코드이다. if문으로 조건을 명시해주었다. 

 

이전 포스팅에서 DFS, BFS 구현을 위해 스택과 큐를 알아보았었다. 이후에 재귀 함수를 알아햐하는 이유는, 재귀 함수의 수행이 스택 자료 구조를 통해 이루어지기 때문이다. 함수를 계속 호출했을 때, 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다. 즉, 재귀 함수는 내부적으로 스택 자료 구조와 동일하다는 것을 기억해야 한다. 따라서 스택 자료 구조를 활용해야 하는 상당수의 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다!

 

재귀함수를 이용하는 대표적 예제: 팩토리얼 문제 

n! = 1*2*3*.........*n(n-1)*n

0!=1!=1 을 종료 조건으로 생각하여 n이 1이하가 되었을 때 함수 종료하도록 하기 

factorial의 의미를 생각하며 구현한 factorial 함수와 재귀함수로 구현한 recur함수의 결과값은 같다. 

하지만 factorial 함수는 반복문이 포함되어 있어 시간 복잡도가 좀 더 크다. 또한 코드가 좀 더 간결함을 알 수 있다. 

 

문제 유형으로 나오는 개념은 아니지만 알아두면 여러 문제가 많이 쓰일 수 있다. 

 

[reference]

도서 "이것이 코딩 테스트다" (https://github.com/ndb796/python-for-coding-test)