재귀함수 매우 간단한 동작과정

재귀함수

• 코딩테스트를 위해 알고리즘 문제를 풀던중 DFS나 DP 분할 정복 등의 문제를 풀다보면 재귀함수가 자주 사용되는 것을 볼 수 있다.
• 기본적으로 재귀함수란 함수 내에서 자기 자신을 호출하는 함수인데, 일반적인 구현 등은 우리가 눈으로 따라가며 동작과정을 생각할 수 있지만 재귀함수가 나오는 순간 이게 어떤 순서로 컴파일 되는지를 몰랐었다.

 

 

재귀함수로 탐색시 고려사항

• 재귀함수를 작성할때는 다음의 조건들을 고려해야한다.

1. 호출시에 수행할 작업을 작성 : 수행작업
2. 호출시에 변경할 값을 작성 : 수행마다 변경해줄 값(상황따라 변경값이 없을 수도 있음)
3. 원하는 답을 찾을 경우 함수를 종료 : 종료조건
4. 조건을 벗어나서 원하는 답을 절대 찾지 못하는 경우 함수를 종료 : 종료조건

 

 

재귀함수 예시

매우 간단한 재귀함수 예제에 대해 이해하시면 완벽히는 아니어도 동작과정을 얼추 할 수 있을것같습니다.

 

만약 다음의 정말 간단한 재귀함수가 있다고 가정해봅니다.

fun repeat(n : Int){
if(n == 0)
return

repeat(n-1)
print(n)
}

매개변수가 0이면 종료하고 아니면 매개변수를 1씩 감소해가며 호출합니다.

 

그리고 main 함수에서 이를 호출해봅시다.

 

fun main(args: Array<String>) {
repeat(3)
}

그럼 어떻게 출력이 될까요? 

123으로 출력이 됩니다.

그럼 이번엔 print문을 호출 위로 옮겨봅시다. 

fun main(args: Array<String>) {
    repeat(3)


}
fun repeat(n: Int){

    if (n == 0) return
    
    print(n)
    repeat(n-1)

}

출력 순서가 바뀐것을 확인할 수 있습니다.

 

차이점을 이해하시면 재귀함수의 동작과정을 얼추 이해하실 수 있을 것같습니다.

 

위 코드의 동작과정

재귀함수로 함수를 호출하게 되면 cpu가 이를 읽기위해 메모리에 해당 함수가 하나 더 잡히게됩니다.

맨 처음 3으로 함수  repeat를 호출 하면 메모리에 아래의 상태로 저장됩니다.

 

1번

fun repeat(n : Int){ // n == 3 
if(n == 0)
return

repeat(n-1)
print(n)
}

그리고 함수 내에서 n-1로 호출 했으니 아래의 함수가 또 메모리에 저장될것입니다.

2번

fun repeat(n : Int){// n == 2
if(n == 0)
return

repeat(n-1)
print(n)
}

또 n-1로 호출 했으니 아래내용이 메모리에 저장됩니다.

3번

fun repeat(n : Int){ n == 1
if(n == 0)
return

repeat(n-1)
print(n)
}

마찬가지로 또 저장됩니다. 

4번

fun repeat(n : Int){ n == 0
if(n == 0)
return

repeat(n-1)
print(n)
}

메모리에는 같은 함수 4개가 순서대로 저장될것입니다. 

마지막 함수에서 n이 0이므로 함수가 return됩니다.

 

함수가 return되면 기존 함수가 메모리에서 삭제되고 함수를 호출했던 곳으로 돌아가게됩니다.

따라서 4번->3번->2번->1번->처음 호출한 main함수의 순으로 돌아갑니다.

이때 return으로 돌아가고나면 처리하지 못한 print문들이 남아있습니다.

따라서 각 함수에서 돌아온 순서대로 출력되어 123으로 출력되는 것입니다.

 

마찬가지의 개념으로 

fun main(args: Array<String>) {
    repeat(3)


}
fun repeat(n: Int){

    if (n == 0) return
    
    print(n)
    repeat(n-1)

}

위의 상황에서는 각각 다음 함수를 호출하기 전에 print로 n을 출력하므로 값이 321이 출력되는 것입니다.

 

정리하면

• 호출시에는 1번->2번->3번->4번의 순으로 호출됩니다.
• 종료조건을 만나 함수가 return되면 4번->3번->2번->1번의 순으로 반환된다고 생각하시면됩니다.
• 호출전에 작성한 코드는 호출되면서 실행되고 호출 다음 적은 코드는 return 되면서 실행됩니다.

 

위의 개념은 재귀함수의 기본 동작과정이고 함수를 계속해서 호출하기때문에 메모리를 계속해서 사용합니다.

따라서 무조건 재귀함수로 구현하기보다는 상황에따라 반복문으로 구현할 수 있으면 반복문으로 구현하는게 좋습니다.

 

추가개념

만약 재귀함수를 호출하는데, return문이 없으면 어떻게 될까?

 

위의 상황에서 return문이 없다면 계속해서 repeat를 반복 호출하다가 stack overflow가 생길것이다.

 

그렇다면 다음의 상황을보자.

class Solution {
    var answer = 0
    var visited = BooleanArray(0)
    fun solution(k: Int, dungeons: Array<IntArray>): Int {
        visited = BooleanArray(dungeons.size)
        
        dfs(0, k, dungeons)
        return answer
    }
    
    fun dfs(depth:Int, p:Int, dungeons: Array<IntArray>){
        for(i in 0 until dungeons.size){
            if(!visited[i] && dungeons[i][0] <= p){
                visited[i] = true
                dfs(depth+1, p-dungeons[i][1], dungeons)
                  visited[i] = false
            }
            
            answer = Math.max(answer, depth)
        }
    }
    
} //프로그래머스 lv2 피로도 문제풀이

위의 코드는 return 없이 재귀를 사용하고 있다. 이는 특정조건에서만 재귀함수를 호출하기때문에 가능하다.

위의 if문에 해당하지않은채 for문을 끝까지 돌게되면 함수 호출이 종료된다.

함수 호출이 종료되면 return과 마찬가지로 이전 상황으로 돌아가 visited[i] = false부터 다시 호출된다.

 

이와같이 끝이 존재하는 재귀함수는 return문 없이도 사용이 가능하다.