피보나치 수

//초기에 작성한 재귀함수 호출 코드
class Solution {
    fun solution(n: Int): Int {
        val answer = temp(n.toLong()) % 1234567L
        return answer.toInt()
    }
    
    fun temp(n: Long) : Long{
        if(n == 0L || n == 1L) return n
         else return temp(n-1L) + temp(n-2L)
    }
}

처음에 해결하려고 하였었던 코드(재귀함수 호출) 이나 런타임에러가 나와 런타임 에러를 해결할 방법을 여기저기

찾아보던 중 for 문과 모듈러 연산의 성질( (A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C )을 사용하여 해결해야된다는 리뷰를 보게 되었고 코드를 수정하여 통과하였다.(접근 방법만 확인하였을 뿐 타인의 코드는 보지 못하였음)

아래가 통과한 코드이며, 작성하고 나서 보니 처음 작성한 코드가 런타임 에러가 날 것 같이 작성한 코드처럼 보이게 되었다. 자료형을 Long 로 변경하면 계산은 가능하지만 숫자가 커짐에 따라 시간이 오래걸릴 수 있기 때문에 temp 함수에서 

리턴시 %1234567 을 하면 어떻게 될지 궁금하여 해보았으나, 똑같이 시간 초과가 나왔으며, 이유를 생각해보니 입력 받는 수가 매우 클 경우 재귀함수가 셀 수 없이 많이 호출되어 시간 초과가 되겠구나 라는 생각이 들었다.

그리고 통과하게 된 코드와 같이 list로 작성 할 경우 입력된 n의 크기만큼 for문이 돌아가는 시간만 걸릴 뿐 추후 값을 찾는 시간은 많이 소요 되지 않기에 시간초과를 하지 않고 통과 할 수 있는 것 같다.

// 최종적으로 통과한 코드
class Solution {
    fun solution(n: Int): Int {
        var temp = mutableListOf(0,1)

        for(i in 2 .. n){
            temp.add( (temp[i-2] % 1234567 + temp[i-1] % 1234567) % 1234567 )
        }
        return temp.last()
    }
}

//통과완료 하고 나서 생각이 들어 수정한 재귀함수 호출 코드
//해당 코드도 마찬가지로 시간 초과 로 인하여 통과하지 못하였음.
class Solution {
    fun solution(n: Int): Int {
        return temp(n)
    }
    
    fun temp(n: Int) : Int{
        if(n == 0 || n == 1) return n
         else return (temp(n-1) % 1234567 + temp(n-2) % 1234567) % 1234567
    }
}