재귀함수란?
하나의 함수 안에서 자신을 다시 호출하는 방식으로 문제를 해결하는 방식
코드를 봤을 때 코드 안에 자신이 다시 호출되는 코드가 존재한다면 이를 재귀함수로 볼 수 있다.
즉, 재귀함수는 반복적인 수행을 해야하는 문제 상황에서 사용할 수 있다. 예를 들어 피보나치나 펙토리얼 등 점화식과 함수의 return 형식이 동일하게 출력할 수 있는 경우에는 재귀함수를 이용하는 것이 오히려 코드 이해를 돕는다.
개인적으로 재귀함수를 완전탐색, DFS, BACK TRACKING, Tree와 같은 알고리즘을 사용해야 할 때 사용한다.
🤪 장점
- 이해하기 쉽다!
- 프로그래밍을 쉽게 할 수 있다!
- 변수 사용을 줄여준다!
만약에 재귀함수를 처음으로 배우는 사람이라면, 위 장점을 공감하기가 쉽지 않을 것이다. 왜냐하면, 필자가 그랬다. 백준에 널려있는 삼성 SW 역량 평가 A형문제 풀이를 보면 대부분 이런 재귀함수를 이용하는 경우가 많다. 그렇다는 것은 많은 사람들이 이해하고 사용한다는 것인데, 명심해야 할 것은 재귀함수가 익숙하지 않다면, 오히려 코드를 이해하는데, 더 어렵다는 것이다. 그렇기 때문에 많은 연습이 필요하다. 어렵다고 안 하진 말자. 재귀함수를 이용해서 풀면 빠르게 끝나는 경우가 많기 때문에 꼭 알아야하는 방법으로 개인적으로 생각한다.
그렇다고 모든 문제를 재귀함수로 접근하여 문제를 풀어하는 것은 아니다. 왜냐하면, 다음과 같은 단점이 존재하기 때문이다.
🤨 단점
- 시간복잡도가 반복문에 비해 계산하기 어렵다.
- 반복문보다 더 큰 오버헤드를 갖는다. 즉 메모리 사용량, 수행시간이 길어질 수 있다.
- 함수 호출을 많이 하기 때문에 StackOverFlow 가능성이 있다.
- 종료 조건을 확실히 해주지 않으면 무한 재귀가 일어난다.
- 4번으로 인해 함수가 그냥 멈춘다.
위와 같은 단점으로 인해 입력값이 정말 많은 알고리즘 문제를 재귀함수로 푸는 것은 매우 좋지 않다. 정지 조건을 아무리 잘 잡았다고 해도 무조건 시간초과가 걸린다.
요즘 코딩테스트에서는 어느 정도 난이도가 있으면 입력값이 100,000으로 주어지는 경우가 대부분이다. 이 데이터를 재귀함수로 다룬다고 생각해보면,,,,, 그렇다.. 문제풀기 매우 까다로울 것이다. 특히나 코드 효율성을 중요시하는 요즘 코테에서는 잘 안맞는 경우가 많다는 것이다.
예로 올해 상반기 K기업에서 진행한 코테에서 그나마 어려웠던 문제를 BACK TRACKING을 이용하여 문제를 풀었다. 답은 무조건 도출되지만, 시간복잡도 측면에서 좋은 코드가 아니기 때문에 절대 제한시간 내에 답을 도출할 수 없다. 참고로 그 문제는 Two Pointer를 이용하여 문제를 풀어야 했었다. 즉 문제를 풀기 전에 입력되는 값으로부터 시간복잡도를 미리 예상을 하고 알맞은 알고리즘을 생각하여 코드를 작성해야 하는 경우에 꼭 재귀함수를 사용해야 하는가?에 대해서 고민해보아야 한다.
우리가 사용할 수 있는 컴퓨터 자원은 한정되어있다. 이를 고려한 코드가 좋은 코드아닐까?
정리
재귀함수 문제를 풀면서 이에 대해 어느 정도 감을 잡아 놓자. 그리고 다른 알고리즘도 알아야 한다. 이때 중요한 것은 재귀함수가 아니라 다른 알고리즘을 사용하면 더 빨리 풀린다면, 주저 없이 해당 알고리즘을 사용하는 것이 알맞다. 맹목적으로 쫓기 보다 필요한 경우에만 사용하자.
예시 코드: Python, Kotlin
Python
# Factorial
def factorial(n):
if n == 1:
return 1
return n * factorial(n-1) Kotlin
fun main(args: Array<String>) {
println(factorial(10))
}
private tailrec fun factorial(n: Int): Int {
if (n == 1) {
return 1
}
return n * factorial(n-1)
}kotlin에서 fun 앞에 tailrec사용하면 콜스택이 생성되지 않는다고 한다. 이런건 참고로 알아두자!
