[Kotlin] 꼬리 재귀 함수 - tailrec

🔷 꼬리 재귀 함수 (tailrec)이란?

    재귀 함수를 구현할 때 마지막(Tail)에 자기 자신을 호출(Recursion)하는 형태의 함수이다.

    반환 값 : 호출 당한 함수의 결과 → 호출한 함수의 결과

 

🔹재귀 함수

        재귀 함수는 '자기 자신을 호출하는 함수'이다.

        구조는 비슷하지만 더 작은 문제로 쪼갤 수 있는 문제를 풀 때 유용한 접근 방법이다. 

 

       함수는 호출될 때마다 함수의 입력값(매개변수), 결과값(리턴값), 리턴 후 돌아갈 위치 등이 스택(Stack)에 보관된다. 

       재귀 함수는 '자기 자신을 호출'을 여러번 반복하여 콜 스택이 깊어질 수록 메모리 오버헤드 (스택 오버 플로우 stack overflow) 현상을 일으킬 수 있다.

    

🔹재귀의 특징

        -  무한 루프에 빠지지 않기 위해 일정한 탈출 조건이 있어야 한다. : base case

        -  코드를 단순화할 수 있다.

        -  재귀 함수는 호출 시마다 스택 공간을 이용하므로 무리하게 호출하면 스택 오버플로우가 일어날 수 있다.

        -  재귀 함수의 호출 횟수는 스택의 남은 공간과 재귀 함수의 지역 변수 사이즈에 따라 달라진다.

        -  디버깅 및 실행 흐름을 파악하기 힘들다.

---

🔷 일반 재귀 함수

호출하면서 계산

        반환하면서 계산을 반복

        호출 당한 함수가 호출한 함수에게 자신의 결과값 전달 -> 전달 받은 함수가 연산 후 다른 함수에게 전달 -> 반복

//   팩토리얼 연산 함수 : 일반 재귀
fun factorial(n : Int) {
    if (n === 1) {
        return 1;
    }
    return n * factorial(n-1);
}

🔹일반 재귀 함수 계산 방식

        factorial(3)
            3 * factorial(2)
                    3 * ( 2 * factorial(1) )
                    3 * ( 2* 1 )
            3 * 2
        6

---

🔷 꼬리 재귀 함수

계산 값 저장 후 한번에 반환

        자신이 호출한 함수한테 받은 결과값에 아무 일도 하지 않고 꼬리(마지막 부분)에서 함수를 호출하는 방식

        연산을 한 후 저장할 데이터 값이 없으므로 메모리 오버헤드 (스택 오버 플로우 stack overflow) 현상 방지

//  팩토리얼 연산 함수 : 꼬리 재귀
tailrec fun factorial(n : Int, total : Int = 1){
    if(n === 1){
        return total;
    }
    return factorial(n - 1, n * total);
}

🔹꼬리 재귀 함수 계산 방식

        factorial(3)
            factorial (2, 3)
                factorial (1, 6)
                6
            6
        6