C++:: 재귀

참고 내용

https://blog.encrypted.gg/943

 

정의

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

핵심

수학적 귀납법으로 생각해야 함.

절차지향식으로 생각하면 머리 터짐!

 

수학적 귀납법

N=1이 성립한다.
N=k가 성립한다면 N=k+1 역시 성립함을 증명하면 N=k가 성립함을 증명할 수 있음

 

알고리즘 틀

1. 함수의 정의 : 함수의 인자로 무엇을 받을지, 함수에서 어디까지 계산하고 자신을 호출할지가 명확해야 함.
   이때, 모든 재귀함수는 반복문만으로 동일한 동작을 하는 함수로 표현할 수 있음.
   (재귀로 할지, 반복문으로 할지 상황에 따라 메모리와 시간의 제약상황에 따라 선택할 수 있다는 뜻)
2. base condition : 특정 입력에 대해 자기 자신을 호출하지 않고 종료되어야 함.
3. 재귀 식

관련 예제

백준 1629 곱셈 : 짝수일 때 바로 반환하는 것, 홀수일 때 한번 더 불러야 함

백준 11729 하노이 탑 : n번째 원판이 이동하는 것을 기준으로 생각하고 출력해야 함.

백준 1074 Z : https://donkeysdevelpment.tistory.com/139