재귀(recursion)

• 재귀란 어떠한 것을 정의할 때 자기 자신을 참조하는 것 을 뜻합니다.

 

 

코드로 한번 보여드리겠습니다.

 

fun main() {
    printNumber(1)
}


private fun printNumber(number : Int) {
    println(number)
    printNumber(number = number + 1)
}

 

printNumber 라는 메서드에 처음 1을 넣고 println 으로 출력 후 다시 printNumber 메서드에 +1 을 해서 실행 합니다.

 

하지만 이렇게 코드를 작성 후 실행하게 되면

 

 

무한루프에 빠지게 되고 결국 콜스택에 메모리가 가득 차서 에러가 발생하게 됩니다.

 

 

• 콜스택

 

함수가 호출이 되면 콜스택에 함수가 쌓이게 되며 함수가 끝난다면 콜스택에서 제거가 됩니다.

 

재귀함수가 호출이 된다면 처음 호출된 함수가 콜스택 가장 밑부분에 쌓이게 되면 위로 계속 재귀로 호출 되는 함수들이 

 

쌓이게 됩니다. 하지만 위에서처럼 무한으로 계속 쌓이게 되면 콜스택에 메모리가 부족하게 되서 에러가 발생하게 됩니다.

 

그래서 일반적인 for문보다 재귀함수가 메모리 낭비가 심할 수 있습니다.

 

 

하지만 왜 재귀함수를 사용하는 것일가요?

 

특수한 경우 재귀함수는 간단하게 문제를 해결 할 수 있게 해줍니다.

 

Factorial 을 예로 들겠습니다.

 

 

fun main() {
    print(factorial(5))
}


private fun factorial(number : Int) : Int {
    if(number <= 1) {
        return number
    }
    
    return number * factorial(number = number - 1)
}

 

 

이렇게 재귀함수를 이용하면 Factorial 을 쉽게 표현할 수 있습니다.

 

위에서 처럼 무한루프에 빠지지 않기 위해 기저 조건을 잘 넣어줘야 합니다. 

 

Factorial 에서는 if 문으로 1이하일 때는 더이상 재귀함수를 호출하지 않게 했습니다.