TIL 웹개발 - 재귀함수, 그저 믿음 뿐
정확히 말하면, 머릿속에 함수 실행 순서를 그리려고 하지 말라는 것이다. 이유는 머릿속에서 재귀에 재귀에 재귀에 재귀를 따라가보면 어는 순간 핀트가 나가버리기 때문이다. 그래서 중요한 것은 재귀 함수의 중요한 부분에 초첨을 맞춰 문제를 풀어나가는 것이다. 재귀가 풀리는 4단계 접근법 재귀를 꼭 써야 하는가? 반복 대신 재귀를 써야하는 경우인지 생각해본다. 재귀함수를 사용해서 푸는 문제의 대부분은 반복을 사용해서도 풀수 있다. 복잡한 문제를 더 작은 문제로 쪼개고, 작은 문제를 반복적으로 풀고, 작은 답들을 조합해서 전체 문제를 해결한다. 그리고 일반적으로 성능은 반복문이 재귀함수보다 더 좋다. 그렇기에 꼭 재귀함수를 써야하는지 먼저 체크해본다. 베이스 조건 답을 바로 알 수 있는 가장 간단한 상황을 생각한다. 재귀함수는 무한루프에 빠질 경우가 많다. 그렇기에 베이스 조건을 가장 먼저 만들어야 한다. 베이스 조건에서 무엇을 return 해야할지 헷갈린다면 문제에서 요구한 답의 데이터 타입을 본다. 예시로 주어진 인풋 값을 보고, 답으로 만드는 방법을 생각하면 함수 실행 순서를 떠올린다. 그보다 문제에 초점을 맞춰 베이스 조건을 만들어보자. 분해 베이스 조건에 가까워지도록 인풋값을 조작한다. 예를 들어, n이라는 정수로 함수를 실행한다면, 자기 자신을 호출할때는 n-1을 넣는다. 그래야 재귀함수가 반복하면서 인풋값이 조금식 더 간단해진다. 재귀적 분해라고도 하는데 인풋값을 간단하게 만들어서 문제를 더 작게 만드는 것이다. 이 재귀적 분해에는 패턴이 보이기도 한다. 정수 : 수를 줄여나간다. n-1 or n-2 배열 : 앞의 숫자를 없애 길이를 줄인다. [1, 2, 3, 4] → [2, 3, 4] → [3, 4] 링크드 리스트 : 포인터가 가리키는 다음 노드가 input으로 들어간다.
