[알고리즘 정리] 재귀

https://blog.encrypted.gg/943

도미노가 모두 쓰러지는지를 설명해보라 한다면 두 가지 방법이 있다.

편의상 앞에서부터 1번, 2번 ... 도미노라 한다면
첫 번째 설명은 1번이 넘어져서 2번이 넘어지고, 2번이 넘어져서 3번이 넘어지고.... 가 반복되서 모든 도미노가 쓰러진다는 설명이다.

두 번째 설명은 수학적 귀납법을 이용한 방법인데 '1번 도미노가 쓰러진다' 와 'k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다' 가 참이니까 모든 도미노가 쓰러진다는 설명 방법이다.

재귀 함수의 조건

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

재귀에 대한 정보 1

함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄 지 명확하게 정해야 함
모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음
재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리, 시간에서는 손해를 봄

재귀에 대한 정보 2

한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있음

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

--> 후에 다이내믹 프로그래밍(DP)로 O(n)으로 해결이 가능하다.

재귀에 대한 정보 3

재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 됨