재귀는 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘입니다.
지금 여기서 제대로 이해를 하고 가야 나중에 재귀를 이용해 문제를 푸는 과정에서 헤매지 않습니다. 우리가 어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것인데 이 귀납적인 방식이란게 지금까지의 우리의 상식과 큰 차이가 있습니다.
올바른 재귀 함수는 반드시 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 합니다. 이러한 입력을 base condition 내지는 base case라고 합니다.그리고 모든 입력은 base condition으로 수렴해야 합니다. 이 코드를 보면 n = 0일 때 자기 자신을 호출하지 않고 종료가 되니 이것이 base condition이고 우리는 이 함수에 자연수만 넣을테니 모든 입력은 결국엔 n = 0으로 수렴하게 됩니다. 이 두 조건 중 어느 하나라도 지켜지지 않는다면 재귀 함수는 결과를 내지 못하고 무한히 들어가다가 런타임 에러가 발생하게 될 것입니다.
먼저 재귀에서는 함수를 명확하게 정의해야 합니다. 정의라는건 함수의 인자로 어떤 것을 받을지, 그리고 어디까지 계산한 후 자기 자신에게 넘겨줄지를 의미합니다. 예시 문제를 풀어볼 때 함수의 형태를 잡는 부분을 계속 강조할 것입니다.
그리고 모든 재귀 함수는 재귀 구조 없이 반복문만으로 동일한 동작을 하는 함수를 만들 수 있습니다. 재귀는 적재적소에 사용하면 코드가 간결해지지만 함수 호출이 꽤 비용이 큰 연산이기 때문에 메모리와 시간에서는 손해를 봅니다. 그렇기 때문에 굳이 재귀를 쓰지 않아도 구현에 큰 어려움이 없으면 재귀 대신 반복문으로 코드를 짜는게 좋지만 재귀 없이 구현을 하면 코드가 너무 복잡해지는 일부 문제들은 재귀로 구현을 하는게 좋습니다.
