재귀함수

• 재귀함수

  • 재귀함수 = 메소드 혹은 함수의 내부에서 자기자신의 메소드 혹은 함수를 다시 호출하는 함수

  • 재귀함수는 언제 사용하는가?

    → 함수 안에서 같은 동작을 반복해야 할 때

  • 재귀함수의 원리

    1. 함수를 만날 때마다 스택에 함수를 올린다

    2. 함수 호출 조건에 더이상 부합하지 않게 되었을 때 함수 호출 중지

       → 함수 종료 조건이 반드시 재귀함수 안에 포함되어야 한다.

    3. 스택의 가장 위에 올려진 함수부터 처리를 반복

  • 재귀함수를 사용하는 이유 = 코드의 간결화 및 변수 사용 최소화

    ⇒ 하지만 메모리 사용이 늘어나므로 풀려는 문제가 재귀를 사용할 수 밖에 없음을 시사하고 스택 오버플로우가 우려되지 않는 경우에만 사용하자.

  • 재귀함수의 대표 사용 예: 팩토리얼, 피보나치 수열, 유클리드 호제법, 하노이의 탑, 8퀸 문제

  • 재귀함수의 깊이: 파이썬은 기본적으로 1000번까지만 호출이 가능하도록 제한

  • 직접재귀와 간접재귀

    • 직접재귀: a() 라는 함수가 반복해서 자기와 똑같은 함수 a()를 호출할 경우
    • 간접재귀: a()가 b()를 호출하고, b()는 a()를 호출하는 과정이 반복되는 경우