재귀함수 알고리즘

바킹독님 알고리즘 영상 참고함

 

 

재귀는 하나의 함수에서 자기자신을 다시 호출하는 알고리즘

• 평소에 코테 문제 풀때 했던 절차적 사고대신 귀납적으로 생각해야함 - 귀납적 사고방식이 필요

도미노를 예로 들면
1번 도미노가 쓰러짐 -> 2번 쓰러짐 -> ..... -> 마지막 도미노가 쓰러짐 - 이게 절차식 사고인거고
귀납적으로 접근하면
1번 도미노가 쓰러짐 -> .... k번째 도미노가 쓰러졌다는 건 k-1번째 도미노는 무조건 쓰러질 것이라고 생각할 수 있음

귀납법이란 ? n=1일 때, 명제 p(n)이 성립한다. n=k일 때, 명제 p(n)이 성립한다고 가정하면 n=k+1일 때도 명제 p(n)이 성립한다
-여기서 k k+1은 너무 집착하지 않아도 됨

재귀 하면 대표문제가 팩토리얼 / 피보나치인데
5! = 4! * 5
4! = 3! * 4
3! = 2! * 3
1 - 끝 // 이렇게 절차 하나하나 따져가면서 구해보지 않아도
(k-1)!이라는 함수를 만들어서 이 함수가 잘 작동한다면 k!이라는 함수도 정확하게 작동할거고, 
여기에 k만 곱해주는 식으로 재귀함수를 만들 수 있다는 걸 의미

• 재귀함수를 만들면서 다시 실행되는 재귀함수가 잘 작동할까?라는 의문을 가지면 안됨 - 잘 만들었다면 어차피 잘 실행될것이기 때문

오버플로우를 막기 위해서 Base condition을 정해줘야 함

계속 자기를 호출하는 시스템이기 때문에 base가 없으면 오류나고, 이 base를 먼저 생각하는 게 문제 접근에 도움이 됨
앞에서 언급했던 팩토리얼을 예로 들면
100! = 100*99*98*....*1 이런 식이기 때문에 아직 코드를 구현하지 않았어도 뭔가 1에서 끝나야 한다는 걸 알 수 있음
(물론 1부터 시작해서 해당 값까지 가도 됨)
그러면 일단 함수를 만들기 전에 
if(조건 === 1){return ~} 이렇게 설정해놓고 조건을 하나씩 줄여나가면서 짜면 되지 않을까?라는 생각을 할 수 있음

★ 제일 중요한 건 함수의 인자로 어떤 것을 받고 어디까지 계산해서 넘겨줄지, base 도착 시 어떤 값을 return할지를 구현하는 것

-이게 사실 핵심이라고 생각(사실 이게 제일 어렵...)