재귀

[ 개념 ]

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

• 귀납적으로 사고하는 방식이 필요(절차지향 사고를 탈피해야함)
  ex1) 도미노 N개가 있을 때 마지막 도미노가 쓰러지는이유 설명!
   1번 도미노가 쓰러지면 -> 2번 도미노가 쓰러진다
   2번 도미노가 쓰러지면 -> 3번 도미노가 쓰러진다
   즉, K번 도미노가 쓰러지면, K+1번 도미노도 쓰러진다!

   ex2) func(n) 일때 어떤 것이 출력이 되는지 설명!

void func(int n){
  if(n == 0) return;
  cout << n << ' ';
  func(n-1);
}

     func(1) -> 1 출력
     func(2) -> 2 1 출력
     ...
     func(k) -> k k-1 k-2 ... 3 2 1 출력

---

[ 재귀함수 조건 ]

1) Base Condition
  : 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다.
2) 모든 입력은 Base Condition에 수렴

  int fibo(int n){
  if(n<=1) return 1; // Base Condition
  return fibo(n-1) + fibo(n-2);
}

---

[ 추가 정보 ]

• 함수의 인자로 어떤 것을 받고 / 어디까지 계산 후 넘겨줄지 명확하게 정해야함
• 모든 재귀함수는 반복문으로 동일한 동작을 할 수 있다.
• 재귀는 반복문으로 했을 때보다 코드가 간결하지만, 메모리 / 시간에서는 손해

• 재귀는 이렇게 비효율적일 수 있다
  

• 재귀함수가 자기 자신을 부를 때 Stack 영역에 계속 누적이 됨
  : 문제의 메모리 제한이 512MB라면 프로그램이 점유하는 메모리가 512MB여야 한다
  그러나, 일부 컴파일 환경에서 Stack영역이 1MB로 제한이 걸려있을 때에는 재귀 사용시 런타임이 발생할 수 있다