[TIL] Kotlin - 재귀 함수, 꼬리재귀 ( Tailrec ) 함수

Topic =  꼬리재귀 함수에 대해서 알아보고 일반 재귀함수, loop 함수와의 차이점을 알아보자.

---

 

 

 

꼬리재귀 함수를 사용하는 이유

 

✅꼬리재귀 함수 개념 정리 이전에 간단한 예제를 통해 꼬리재귀 함수를 사용하는 이유에 대해 작성해볼 것.

 

아래 3 가지 방식의 코드는 모두, 두 정수 a, b 의 최대 공약수를 리턴하는 함수이다. 

• 가독성이 좋은 코드는? = 재귀함수
• 메모리 효율성이 좋은 코드는 ? =  loop 함수
• 가독성도 좋고, 메모리 효율성도 좋은 방식 ? = 꼬리재귀 함수

 

[ 코드 1. 재귀 함수 ]

fun gcd(a: Int, b: Int): Int {
    if (b == 0) return a
    return gcd(b, a % b)
}

 

 

[ 코드 2. loop ( while ) 함수 ]

fun gcd2(a: Int, b: Int): Int {
    var a = a
    var b = b

    while (b != 0) {
        var temp = b
        b = a % b
        a = temp
    }

    return a
}

 

 

[ 코드 3. 재귀함수 ( tailrec ) ]

tailrec fun gcd(a: Int, b: Int): Int {
    if (b == 0) return a
    return gcd(b, a % b)
}

 

 

❓꼬리재귀 함수가 재귀 함수와 loop 함수의 장점을 갖을 수 있는 이유

 

➡️ 컴파일 전에는 가독성이 좋은 재귀함수 형태로 보이지만, 컴파일 시 메모리 효율성이 좋은 최적화된 loop 함수로 자동 변환되기 때문이다.

 

 

 

 

재귀 함수, 꼬리재귀 함수

[ 재귀 함수 ]

재귀 함수란, 함수 내에서 자기 자신을 호출하는 방식으로 작동하는 함수들을 재귀 함수라고 한다. 기본적인 단순 재귀 함수는 각 호출마다 문제의 크기를 줄여 나가면서 결국엔 재귀 함수 내에서 지정한 기본 경우( basecase ) 에 도달하여 재귀 호출이 종료되는 구조이다.

 

🟩 장점

 반복문으로 작성하는 것보다 코드 작성량도 짧고, 가독성이 좋다

 

🟥 단점

재귀 함수 자체가 함수를 여러번 호출하는 것이 되므로, 기본적으로 함수가 호출될 때, 함수의 정보 데이터 [ 매개변수 ( 입력 값 ) , 지역변수, 리턴 값, 반환 주소 등 ] 를 메모리의 스택 프레임에 저장한다. 때문에 단순 재귀 함수가 자기 자신을 호출하여 문제의 크기를 줄여 나갈 때마다 스택 영역의 메모리 데이터가 쌓이게 된다. 이는 함수 실행이 많아지게 될 경우 스택 메모리 영역이 다 차버리는 StackOverflow 현상이 일어날 수 있다.

 

[ 꼬리재귀 함수 ]

꼬리재귀 함수는 함수 내에서 자기 자신을 호출하는 것은 단순 재귀 함수와 같지만, 꼬리재귀 함수는 함수의 마지막 동작이 자기 자신을 호출하는 경우에 tailrec 키워드를 붙여 컴파일 시 꼬리재귀 함수를 loop 반복문으로 최적화하여 변환한다. 컴파일 시 loop 문으로 변환하기 때문에 StackOverflow 의 위험 없이 효율적인 동작이 가능하다.

 

 

꼬리재귀 함수 In Kotlin

 

Kotlin 은 기존 단순 재귀 함수에 tailrec 키워드를 붙임으로써 컴파일러에게 꼬리재귀 함수임을 알려 사용하며, 꼬리 재귀 함수의 조건을 충족하지 않을 경우, 꼬리 재귀 함수 요건이 충족되지 않았음을 알려준다.

꼬리 재귀 함수 요건이 충족되지 않았을 경우 경고.

 

 

 

 

 

 

 

 

 

 

---

 

[ A. 오늘 복습한 내용 / B. 새로 알게된 키워드 ( 추후 학습해보기 ) ]

A. Null

 

B. 꼬리 재귀 외에도 재귀 함수의 여러 종류 [ 상호재귀, 중첩재귀, 간첩재귀, 백트래킹 ] 

 

B. 메모리 영역에 컨텍스트가 쌓인다고 함. → 컨텍스트 스위칭

 

---

 

[느낀 점]

1. 재귀 함수를 학습해보니까 잘 사용하기만 하면 코드가 간결해지고 보기 좋아져서 굉장히 매력적인 것 같다 자주 사용해보면서 익숙해져봐야겠다.

 

2. 새로 알게된 키워드들이 생길 때마다 깊게 학습해보고 싶은데, 그 개념들에 필요한 사전 지식이 없어서 진입하기가 꺼려진다. 그럼에도 학습해보면서 여러 학습 키워드를 넓혀 나가야 할지, 여러 키워드 들을 간단하게 학습 후 연결되는 내용들을 깊게 파고 들어야 할지를 고민하는데 시간이 많이 들어가서 문제인 것 같다.

 

3. 업무 보면서 학습하고, 학습하면서 정리해본 글을 블로그에 올리는데 시간이 부족하다. 마음 같아서는 빨리 빨리 여러 개념을 학습하고 싶은데, 학습 속도도 느린 느낌이다.

 

 

---

[Reference]

What is the point of tailrec in Kotlin?