참고문헌

재귀

정의

  • 자신을 정의할 때 자기 자신을 재 참조하는 방법
  • func 이라는 함수를 정의할 때, func 함수 안에 func 을 호출하고 그 호출 한 func 안에 func 을 참조하는 방법

주의할 점

  1. Stack OverFlow

    • 재귀호출이 너무 반복적으로 되면, 즉 재귀가 깊어지면 자바에서는 Stack OverFlow 라는 에러를 뱉는다.
    • 함수를 반복적으로 호출하는 만큼 메모리에 스택이 되기 때문에 결국 메모리를 엄청나게 차지하게 된다.
    • 재귀함수가 끝날 때는 함수를 닫으면서 스택된 메모리에서 pop 을 하기때문에 수행시간 또한 매우 느려진다.
    • 위 이유에서, 재귀호출은 평상시에 알고리즘 자체가 재귀가 자연스럽거나 호출을 많이 하지 않는 범위일 때 쓰이고 그 외에는 자주 쓰이지 않는다.

  2. 무한루프

    • 재귀 함수가 끝나는 지점을 정확하게 구현해야한다.
    • 재귀에서는 끝나는 지점이 명확하지 않으면 자칫 무한루프에 빠지기 쉽다.

  3. 반복문으로 대체가능

    • 재귀로 풀 수 있는 문제는 거의 대부분 반복문으로 대체하여 풀 수 있다.

적용 사례

  • 재귀의 개념이 가장 많이 적용되는 부분은 수식적으로 점화식을 표현할 수 있다던가, 일정한 패턴을 갖을 때가 많다.
  • 특히 '순회' 또는 '탐색'이라는 것을 배울 때 자주 써먹을 것이다 : 그래프 탐색(DFS, BFS)이나 정렬을 구현할 때