재귀적으로 사고하기: 기본과 재귀 호출

재귀는 더 작은 조각에 대해 자기 자신을 호출하여 문제를 해결하는 함수입니다. 조각이 직접 답할 수 있을 만큼 작아질 때까지 반복합니다. 🌀

핵심적인 사고방식은 믿음의 도약입니다. 재귀 호출이 더 작은 입력에 대해 이미 올바르게 작동한다고 가정한 다음, 그 결과 위에 답을 쌓으세요.

기저 사례는 재귀 호출 없이 답하는 가장 작은 입력입니다. 이것이 없으면 함수가 영원히 자기 자신을 호출하다가 중단됩니다.

재귀 사례는 문제를 줄인 뒤 더 작은 버전에 대해 자기 자신을 호출합니다. 각 호출은 기저 사례에 가까워져야 합니다.

여기서 팩토리얼은 두 부분을 모두 보여 줍니다. 0에서 멈추는 기저 사례와 n에서 1을 뺀 값에 대한 재귀 호출입니다.

각 호출은 내부 호출이 반환될 때까지 호출 스택에서 기다립니다. 가장 깊은 호출이 먼저 끝나고, 그다음 결과가 스택을 거슬러 올라오며 반환됩니다.

Python은 기본적으로 재귀 깊이를 약 1000으로 제한합니다. 깊은 경시대회 재귀에서는 실행 시간 오류를 피하려면 sys.setrecursionlimit을 사용해야 합니다.

올바른 재귀는 항상 입력을 기저 사례를 향해 줄입니다. 같은 크기의 입력을 다시 전달하면 무한히 반복됩니다. ⚠️

이 재귀적 합은 첫 번째 요소를 떼어 내고, 나머지 목록을 더하는 일은 호출에 맡깁니다.

함수가 두 번 이상 호출되면 작업이 재귀 트리를 이룹니다. 트리의 크기를 보면 전체 비용을 알 수 있습니다.

순진한 피보나치는 같은 값을 계속해서 다시 계산하므로 지수 시간이 걸립니다. 그 결과를 메모이제이션하면 이 문제를 즉시 해결할 수 있습니다.

재귀 함수에 기저 사례가 없으면 어떻게 될까요?

재귀에는 멈추기 위한 기저 사례와 입력을 줄이는 재귀 사례가 필요하다는 것을 배웠습니다. 더 작은 호출을 믿고 맡기면 나머지는 자연스럽게 따라옵니다. 🎯