/* 본 게시물은 ' ' 의 내용을 토대로 작성되었습니다. */
참고 자료
[BoostCourse - cs50 - 재귀] : https://www.boostcourse.org/cs112
#재귀
우리는 알고리즘을 구현하기 위해 코드를 작성하다 보면 동일한 작업을 반복해야 할 때가 있다. 보통 이러한 작업은 함수로 구현하여 코드를 보다 효율적으로 만들 수 있다. 하지만 함수 내에서도 동일한 작업이 반복되는 경우는 어떻게 할까? for문이나 while 문으로 반복을 구현할 수도 있지만 이번에 배울 '재귀' 를 통해 함수 내에서 반복을 만들 수 있다. 재귀에 대해 배워보자.
1. 재귀란?
재귀의 사전적의미는 어떠한 것을 정의할 때 자기자신을 참조(호출)하는 것을 뜻한다. 즉, 알고리즘에서 재귀란 함수를 함수 내에서 재사용하는 방법이다. (loop 말고 다른 방법이라고 생각하자)
우리는 함수를 보통 main 함수 안에서 프로그램을 작성하면서 필요한 순간에 호출하여 사용한다. main 역시 함수인데 다른 함수를 호출하여 사용하는 것을 보고 '함수가 본인 스스로를 호출해서 사용할 수 있을까?' 라는 의문을 가질 수 있다. 이에 대한 답은 '가능' 이다.
재귀 함수는 반드시 다음 조건에 맞게 설계해야한다. 그렇지 않으면 스택 오버플로 오류가 발생하여 프로그램이 제대로 동작하지 않게 된다.
재귀 함수의 조건
- 무한 호출에 빠지지 않도록 탈출 조건을 만들어야 한다.
- 스택 영역을 이용하므로 호출 횟수를 무리하게 많이 지정해 연산하지 않는다.
- 코드를 복잡하지 않게 한다.
2. 재귀함수 예시
예시를 통해 재귀 함수를 알아보자.
1. factorial
factorial 을 loop 와 재귀를 이용해서 구현해보자.
루프를 이용한 factorial
fun factorialLoop(n: Int) {
var result = 1
for (number in 1..n) {
result *= number
}
println("factorial - loop : $result")
}재귀를 이용한 factorial
fun factorialRecursion(n: Int, result: Int = 1) {
return if (n <= 0){ //탈출 조건
println("factorial - recursion : $result")
} else{
factorialRecursion(n-1, n*result)
}
}
실행 결과
사실 코드만 봐서는 재귀가 어떻게 돌아가는지 이해가기가 어렵다. 재귀가 어떻게 돌아가는지 알아보자.
재귀 함수를 이해하기 위해서는 스택 에 대한 이해가 필요하다.
cf> 스택
재귀 함수에서 동일한 함수를 계속해서 호출될 때마다 함수를 위한 메모리가 계속해서 할당된다. 함수가 호출될 때 마다 사용되는 메모리를 스택이라고 한다. 스택은 선입후출로 차례대로 쌓고 위에서 부터 종료하는 특징을 갖고 있다. 우리가 사용하는 운영체제에서는 함수를 실행할 수 있는 공간(스택들을 쌓는 공간)이 정해져있는데, 재귀함수가 계속해서 함수를 호출하다보면 스택이 스택 공간을 초과하여 프로그램이 충돌이 발생한다. 이를 '스택오버플로우' 라고 한다.
재귀함수 호출 과정에 관한 글들을 읽어보던 중 기초 개념을 정리해놓은 글 [SoniaComp - 자료구조 - 재귀호출]을 찾았다.
이런 스택의 개념을 완전히 이해한다면 다음 두 팩토리얼 코드의 차이를 알 수 있을 것이다.
//version 1
fun factorialRecursion(n: Int, result: Int = 1): Int {
return if (n <= 0){
result
} else{
factorialRecursion( n-1, n*result)
}
}
//version 2
fun factorialRecursion3(n: Int): Int {
if (n <= 1){
return 1
}
return n * factorialRecursion3(n-1)
}두 코드의 차이점은 함수의 파라미터로 결과값을 주느냐 안 주느냐의 차이이다. 눈치 챘을지 모르겠지만, version 1(파라미터로 결과 값을 전달)는 스택을 쌓는 과정에서 계산을 해서 스택이 사라지는 과정에서는 result의 값만 반환한다.
즉, 스택의 정상에서 이미 결과를 보고 그 결과를 가지고 내려온다고 보면된다.
반대로 version 2(파라미터로 결과 값 전달 x)는 스택이 사라지는 과정에서 계산을 진행한다. 정상에서 1이라는 값을 받아 내려오면서 1*2*3*...*n 계산하여 최종적으로 마지막 스택이 사라지는 과정에서 결과를 얻을 수 있다.
첫 번째 방법을 공재귀라고 한다. 공재귀는 재귀의 각 단계를 즉시 계산한다. 즉, 계산을 한 번에 한 단계씩 수행한다.
두 번째 방법은 재귀이다. 재귀는 최종 조건에 도달할 때까지 계산이 미뤄진다.
그러면 계산은 누가 더 빠를까?
재귀가 공재귀 보다 빠르다. 하지만 두 방법 모두 재귀의 한계인 스택 오버플로우는 넘지 못한다.
3. 재귀함수는 왜 사용할까?
내가 처음 재귀함수를 배웠을 때 '반복문을 두고서 재귀를 사용할 필요가 있을까?' 라는 생각을 했다.
이에 대한 답은 다소 허무했다.. (보기 좋아서..)
재귀 함수의 장점
- 반복문에 비해 재귀 함수는 상대적으로 간결한 코드로 작성할 수 있다.
재귀 함수의 단점
- 메모리를 많이 사용한다. (스택을 사용하므로)
- 속도가 상대적으로 느리다.
재귀 함수가 반복문보다 느린 이유에 대해서 간단히 설명해보겠다. 반복문은 동일한 변수를 지속적으로 사용하기 때문에 새로운 함수를 호출하는 비용이 안든다. 하지만 재귀함수에서는 함수를 호출하면서 context switching 비용이 발생하기 때문에 반복문에 비해 속도가 느리다.
하지만 반복문을 사용하면 하나의 스택에 모든 것을 처리해야하므로 여러 변수들을 선언하고 재귀에 비해 코드가 길어진다.
<요약>
성능을 중요시 하면 반복문, 코드의 간결성을 중요시 하면 재귀
cf> 재귀 함수의 단점을 해결하는 방법
소프트웨어 엔지니어들은 재귀 함수의 장점과 반복문의 장점 두 개 모두 얻을 수 있는 방법에 대해 고민했고 이에 대한 답으로 나온 것이 바로 '꼬리 재귀' 라는 기법이다. 이는 컴파일 과정에서 꼬리 재귀 코드를 보고 컴파일러가 적절한 반복문으로 컴파일 해주는 방법이다. kotlin 에서는 tailrec 키워드를 함수 앞에 쓰면 컴파일러가 알아서 재귀 함수를 반복문으로 고쳐준다. (그 대신 재귀 함수 형태는 공재귀만 가능하다) 이를 통해 코드를 재귀의 간결한 코드로 스택 오버플로우의 한계를 극복했다.
꼬리 재귀 함수를 한 번 사용해보자.
// 꼬리 재귀를 이용한 factorial -> 컴파일 과정에서 반복문으로 바뀜
tailrec fun tailFactorialRecursion(n: Int, result: Int = 1): Int {
return if (n <= 0){
result
} else{
factorialRecursion(n-1, n+result)
}
}
스택 오버플로우가 일어나지 않고 값을 출력하는 것을 볼 수 있다.
그렇다면 공재귀가 아닌 재귀 형태의 함수에 tailrec 을 붙이면 어떻게 될까?
// 재귀 함수 앞에 tailrec 붙임
tailrec fun tailfactorialRecursion2(n: Int): Int {
println(n)
if (n <= 1){
return 1
}
return n * tailfactorialRecursion2(n-1)
}
tailrec 키워드가 앞에 붙어도 재귀 형태의 함수는 반복문으로 못 바꾸고 재귀로 실행한다.
(kotlin에는 tailrec 키워드 말고도 인라인, 내부, reified, open override 등 매우 유용한 수정 키워드가 많이 있다. 이들도 나중에 한 번 다뤄보겠다.)
재귀 끝.. 더 이상 재귀가 무섭지 않다!
2021 / 09 / 07
