[알고리즘/C++] 재귀

- 재귀 : 함수가 자기 자신을 다시 호출

//ex. 1부터 N까지의 합을 구하는 함수
int func(int N){
  if(N == 0) return 0
  return func(N-1) + N;
}

- 재귀의 풀이 - 수학적 귀납
  - ex. 도미노 : 1번 도미노는 쓰러진다 > k번 도미노가 쓰러지면 k+1번 도미노가 쓰러진다
  - 1부터 N까지의 계산
    - func(1)은 1을 출력한다
    - func(k)는 k ~ 1까지의 합을 출력
    - func(k+1)은 k+1 ~ 1까지의 합을 출력 : func(k+1)은 func(k)를 출력 - k+1과 k~1까지의 합

- 재귀 함수의 조건
  - 특정 입력(base condition)의 경우 종료
  - 모든 입력은 base condition으로 수렴해야 함
  - 재귀는 코드는 단순 / 메모리와 수행시간에는 손해

//ex. 1부터 N까지의 합을 구하는 함수
int func(int N){
  if(N == 0) return 0 // base condition
  return func(N-1) + N; //모든 N은 0으로 수렴
}