재귀 함수 알고리즘 .

 

아래 블로그 참조

https://itandhumanities.tistory.com/27

[코틀린을 다루는 기술] Kotlin에서의 재귀 함수 사용

 

재귀함수를 알아보기 전에 팩토리얼 함수를 알아보자 .

팩토리얼 함수란 특정값에서 1까지 모두 곱하는 연산을 의미한다. 

 

예를들어 특정함수가 10 이라고 한다면 10x9x8x7x6x5x4x3x2x1 의 값을 구하는 것을 의미한다.

private fun factorial(n: Int): Long {
    return if (n == 1) { 1이 되었을 때 종료
        n.toLong()
    } else { // 1이 되기 전 까지 반복
        n * (factorial(n - 1))
    }
}

 

 

위의 함수를 사용하자면 아래와 같이 사용할 수 있다. 

private fun solution(n: Int) {
    val result = factorial(n)
}

 

하지만 이렇게 사용하게 되었을 때 팩토리얼 함수는 10번이 호출이 되고 (특정값이 10이라고 가정했을 때) 메모리 스택 또한 10배 사용되어진다고 한다. 그래서 사용할 수 있는 것이 공재귀 라는 것 인데. 공재귀란 계산을 한 단계씩 수행하면서 최종 조건에 도달할 때 까지 계산을 미뤘다가 조건에 도달했을 시 결과를 도출한다고 한다. 

 

이런식으로 현재 값을 넣어주어 공재귀를 만들어준다. 

private fun recursive(n: Int, res: Int): Int =
    // res = 초기 설정 값 

    if (n == 1) res // 빠져나갈 조건 설정
    else { // 조건 충족 안됐을 시 재귀 .
        recursive(n - 1, n * res)
    }

 

 

아래와 같이 사용할 수 있다.

private fun solution(n: Int) {
    val result = recursive  (n, 1)
}

 

 

재귀함수의 중요한 부분은 꼭 재귀를 탈출할 수 있는 조건을 만들어줘야한다는 것과 

다른 것으로는 자기 자신을 포함해서 계산을 한다는 것이다.