자료구조/알고리즘

• 재귀(Recursion)

  : 자기 자신을 호출하는 함수

  • 재귀 함수의 장점

    • 여러 개의 반복문을 사용하지 않기 때문에, 코드가 간결해지고 수정이 용이하다.
    • 변수를 여러 개 사용할 필요가 없다.

  • 재귀 함수의 단점

    • 반복문과 달리, 코드의 흐름을 직관적으로 파악하기 어렵다.
    • 반복적으로 메서드를 호출하며 지역변수, 매개변수, 반환값을 모두 stack에 저장하기 때문에, 반복문에 비해 메모리를 더 많이 사용한다.
    • 메서드를 호출하고 메서드가 종료된 이후 복귀를 위한 컨텍스트 스위칭 비용이 발생한다.

  • 재귀 함수를 사용하기 위한 조건

    • 문제의 크기를 점점 작게 쪼갤 수 있어야 한다.
    • 재귀 호출이 종료되는 시점이 존재해야한다.

  • 재귀 함수 동작 과정

  1. 재귀 함수의 입력값과 출력값 정의하기
  2. 문제를 쪼개고 경우의 수를 나누기
  3. 단순한 문제 해결하기 (base case: 재귀의 탈출 조건을 구성)
  4. 복잡한 문제 해결하기 (나머지 복잡한 경우를 해결)
  5. 코드 구현하기