재귀 Recursion

재귀 함수의 조건

• 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함(Base Condition)
• 모든 입력은 Base Condition으로 수렴해야 함

재귀에 대한 정보

• 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 함.
• 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음
• 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간에서는 손해를 봄
  • 재귀 함수 호출은 호출 스택(call stack)에 새로운 프레임을 계속해서 추가하므로 오버헤드 발생
  • 깊은 재귀 호출이나 재귀 호출이 많은 경우 메모리 사용량이 증가, 스택 오버플로우 발생 가능
• 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있음
  • fibonacci 함수를 예로 들면, n번째 항의 값을 계산하기 위해 이미 계산한 값을 다시 계산하는 일이 빈번하게 일어남
  • 자기 자신을 여러 번 호출하는 과정에서 중복된 계산이 계속 발생해 시간복잡도가 매우 커질 수 있다.
    • 다이나믹 프로그래밍 기법으로 해결할 수 있음.
• 재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적됨
  • 메모리의 스택 영역에 함수에 대한 정보가 누적된다.