대부분의 재귀 함수가 루프로 작성 될 수있는 방법을 논의하는 비디오가 this 인 것을 보았습니다. 그러나 그것에 대해 생각할 때 나는 둘 사이의 논리적 인 차이를 볼 수 없었습니다. 여기서 this 주제를 찾았지만 웹상의 다른 많은 비슷한 주제와 마찬가지로 실용적인 차이에만 초점을 맞추기 때문에 루프와 재귀가 처리되는 방식의 논리적 인 차이점은 무엇입니까?루프와 재귀 함수의 논리적 차이점은 무엇입니까?
하단 라인 재귀 - 재귀는보다 다양하지만 실제로는 일반적으로 반복보다 효율적이지 않습니다.
루프는 원할 경우 원칙적으로 항상 재귀로 구현 될 수 있습니다. 실제로 스택 리소스의 한계는 해결할 수있는 문제의 크기에 심각한 제약을가합니다. 나는 수십억 번 반복하는 루프를 만들 수 있고 컴파일러가 루프를 반복 할 수 있는지 확신 할 수 없다면 결코 재귀를 시도하지 않을 수도 있습니다. 스택 제한과 효율성으로 인해 사람들은 순환에 해당하는 재귀를 찾으려고합니다.
꼬리 재귀는 항상 루프로 변환 될 수 있습니다. 그러나 변환 할 수없는 재귀가 있습니다. 예를 들어, 나는 실험의 통계적 설계를 사용한다. 때로는 큰 디자인이 여러 개의 작은 하위 디자인을 "교차"하여 구성됩니다. Crossing은 두 번째 디자인의 모든 행을 첫 번째 행의 각 행에 연결하는 곳입니다. 두 개의 하위 디자인의 경우이 모든 요구 사항은 단순한 중첩 루핑이지만 세 가지 이상의 디자인의 경우 중첩 수준을 높이고 각각의 추가 하위 디자인마다 한 수준의 중첩을 추가해야합니다. 그래서 이것은 원칙적으로 중첩 된 루핑이지만 실제로는 중첩의 양은 가변적입니다. 루핑을 사용하여 구현하려는 경우 다른 하위 디자인을 교차 할 때마다 중첩 루프를 추가/제거하기 위해 프로그램을 수정해야하므로 불변 루프 기반을 작성할 수 없습니다 번역. 재귀를 통해 쉽게 구현할 수 있습니다. 이 경우 6 년 전에 코드를 작성하고 디버깅했기 때문에 약간의 효율성을 교환하게되어 기쁘게 생각합니다. 그 이후로 다양한 복잡성을 가진 교차 디자인을 많이 만들었으므로 수정하지 않아도됩니다.
재귀 또는 반복의 선택은 문제가 해결되는 방법에 대한 생각에 달려 있습니다. 어떤 "사고 방식"은 자연스럽게 반복적 인 해결책으로 이어지고 다른 사고 방식은 반복적 인 해결책으로 이어집니다. 어떤 문제에 대해서도 원칙적으로 재귀 적 솔루션이나 반복적 인 솔루션을 제공하는 방식으로 생각할 수 있습니다. 반복 솔루션은 재귀 스택의 시뮬레이션을 끝내기도하지만 실제 재귀는 없습니다.
다음은 예제입니다. 정수 배열 (양수 또는 음수)이 있고 최대 세그먼트 합계를 찾고 싶습니다. 세그먼트는 인접한 배열 조각입니다. 따라서 배열 [3, -4, 2, 1, -2, 4]에서 최대 세그먼트 합은 5이고 세그먼트 [2, 1, -2, 4]에서 얻습니다. 그것의 합계는 5입니다.
OK - 어떻게이 문제를 해결할 수 있습니까? 당신이 할 수있는 한 가지는 다음과 같은 이유입니다. "왼쪽 절반의 최대 세그먼트 합계와 오른쪽 절반의 최대 세그먼트 합계를 알고 있다면 어쩌면 그 둘을 함께 잼으로써 최대 세그먼트 합계를 계산할 수 있습니다. . 이 아이디어는 두 subhalves에 대한 최대 세그먼트 합계를 찾아야하며, 이것은 원래 문제의 작은 인스턴스입니다. 이것은 재귀입니다. 따라서이 아이디어를 코드로 직접 변환하면 재귀 적으로 사용될 것입니다.
그러나 최대 세그먼트 합계 문제는 "재귀 적"또는 "반복적"이 아닙니다. 해결책에 대한 생각에 따라 둘 다 될 수 있습니다. 위의 재귀 적 사고 프로세스를 제공했습니다. 다음은 반복적 인 프로세스입니다. "일부 인덱스 i에서 시작하여 일부 인덱스 j에서 끝나는 각 세그먼트에 요소를 추가하면 이러한 문제를 해결하기 위해 최대 개수를 취할 수 있습니다."그리고이 접근법을 직접 코딩하려고 시도하면 중첩 된 중첩 루프가 생기게됩니다 (할당량이 너무 비효율적이기 때문에 과제에 나쁜 표시가됩니다).
따라서 문제를 개념화하는 방법에 따라 같은 문제가 재귀 또는 반복적 인 해결책으로 이어질 수 있습니다. 이제는 여러 가지 방법으로 해결할 수있는 문제가있는 곳과 합리적인 재귀 적 반복 솔루션이있는 곳을 선택했습니다. 그러나 일부 문제는 한 가지 유형의 솔루션 만 허용하며 해당 솔루션은 재귀 또는 반복을 사용하여 가장 자연스럽게 구현 될 수 있습니다. 예를 들어 y 또는 n을 입력 할 때까지 사용자에게 문자 입력을 계속 요청하는 함수를 작성하도록 요청한 경우 "프롬프트를 반복하고 입력을 요청합니다 ..."라고 생각하기 시작할 수도 있고 사용자가 알기도 전에 몇 가지 반복 코드가 있습니다. 아마 당신은 재귀 적으로 생각할 것입니다 : "사용자가 y 또는 n을 입력하면 끝났습니다. 그렇지 않으면 사용자에게 y 또는 n"을 묻습니다.이 경우 재귀 알고리즘을 생성합니다. 그러나 여기에 재귀를하면 많은 도움이되지 않습니다. 불필요하게 스택을 사용하므로 프로그램이 더 빨라지지는 않습니다. 재귀를 사용하면 정확성을 쉽게 증명할 수 있습니다. 반복적으로 합리적인 반복 솔루션을 제공 할 수있는 경우에도 재귀 적으로 표현할 수 있습니다.