재귀

자신을 포함하는 정의

• 조상(ancestor)이 무엇인지 어떻게 정의할 수 있는가? 당신의 부모는 조상이다. 또한 부모의 조상도 조상이다. 이 두 문장은 무한한 사슬을 정의하며, 두 번째 문서는 그 자체가 정의하는 단어를 사용하고 있다.
• 이는 순환 논리가 아니다. 첫 번째 문장이 사슬이 멈출 수 있는 지점을 제시하기 때문이다. 이것이 없다면 정의는 끝없이 풀려 나가게 된다.
• 프로그램은 같은 방식으로 작성될 수 있으며, 이러한 사슬 형태로 형성된 문제에 대해 재귀적 해법은 루프보다 현저히 짧다.
• 이 수업은 기본 경우(base case) 와 재귀적 경우(recursive case), 재귀 호출이 추적되는 방식, 그리고 아래에서 호출 스택(call stack) 이 무엇을 하는지 다룬다.

두 가지 경우

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
    IF n = 0 OR n = 1 THEN
        RETURN 1                          // base case
    ELSE
        RETURN n * Factorial(n - 1)       // recursive case
    ENDIF
ENDFUNCTION

• 기본 경우는 더 이상 호출 없이 직접 답할 수 있을 만큼 작은 문제의 버전이며, 이것이 재귀를 멈춘다.
• 재귀적 경우는 더 작은 입력으로 함수를 다시 호출하여 기본 경우로 나아가게 한다.
• 둘 다 필요하다. 기본 경우가 없는 재귀는 절대 멈추지 않으며, 입력이 shrinking되지 않는 재귀는 기본 경우에 도달하지 못한다.

worked example: 재귀 추적(tracing)

기계가 하는 일

• 각 호출은 개별적인 매개변수와 로컬 변수의 복사본을 필요로 한다. 왜냐하면 Factorial(3)과 Factorial(2)은 서로 다른 n 값을 가진 별개의 호출이기 때문이다.
• 이 복사본들은 호출 스택(call stack) 위의 스택 프레임(stack frame) 에 위치한다: 진행 중인 호출마다 하나의 프레임이 있으며, 매개변수, 로컬 변수, 반환 주소를 담고 있다.
• 프레임은 각 호출 시 밀어放入(pushed) 되고, 반환 시 꺼냄(popped) 된다. 이것이 값들이 호출된 순서의 역순으로 돌아오는 이유이다: 호출 스택은 정확히 주제 10의 ADT인 스택이다.

문제가 발생하는 경우

• 기본 CASE가 없거나 도달할 수 없는 기본 CASE: 재귀가 멈추지 않으며 프레임이 쌓이고 호출 스택의 메모리가 고갈된다. 이를 스택 오버플로우(stack overflow) 라고 한다.
• 깊은 재귀:百万 번의 레벨에 대한 올바른 재귀even도 million frames를 필요하므로, 루프에서는 사용하지 않는 메모리를 소모할 수 있다.
• 중복 작업:-naive recursive Fibonacci는 동일한 값을 지수적으로 많은回数重新计算。루프로 수정하거나, 메모이제이션(memoisation) 을 사용하여 계산된 결과를 처음에 저장함으로써 해결한다.

재귀 또는 반복(iteration)

• 재귀는 자기 유사(self-similar) 문제에 적합하다. 즉, 문제가 자체의 더 작은 복사본을 포함하는 경우: 트리 Traverse, 이진 검색 및 병합 정렬과 같은 분할 정복(divide and conquer), 그리고 위 조상 사슬.
• 반복(iteration)은其余 everything에 적합하며, 반복에 대해 추가 메모리를 사용하지 않는다.
• 모든 재귀적인 것은 반복적으로 작성할 수 있으며, 그 반대도 true이다. 선택은 스택 비용이라는 메모리와 대비하여 어떤 것이 문제를 명확하게 표현하는지에 관한 것이다.

worked example: 위험을 서술하라

놓칠 수 있는 점

이해했습니다