[바킹독의 실전 알고리즘] 재귀

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

📍 귀납적 사고를 해야함!

• 절차지향적 사고
  
• 귀납적 사고
  : base condition을 잘 잡아놓고, 2k, 2k+1의 결과를 계산하는 사고방식
  

1. 함수의 형태를 잡는 것이 명확해야 함
2. 반복문으로도 같은 동작을 하도록 할 수 있음 (메모리/시간에서 손해를 봄)
3. 자기 자신을 여러번 호출하게 되면 계산 중복으로 비효율적일 수 있음 (e.g. 피보나치 수열)
4. 자기 자신을 호출하면 스택 영역에 계속 누적됨