while 루프가 본질적으로 재귀인지 궁금합니다.
while 루프는 마지막에 자신을 호출하는 함수로 볼 수 있기 때문이라고 생각합니다. 재귀가 아닌 경우 차이점은 무엇입니까?
답변
루프는 재귀가 아닙니다 . 실제로, 그것들은 반대 메커니즘 의 주요 예인 반복 입니다.
재귀의 요점은 처리의 한 요소 가 다른 인스턴스를 호출 한다는 것입니다. 루프 제어 기계는 단지 점프 가 시작 지점으로 돌아.
코드에서 뛰어 내리고 다른 코드 블록을 호출하는 것은 다른 작업입니다. 예를 들어, 루프 시작으로 점프 할 때 루프 제어 변수는 여전히 점프 이전과 동일한 값을 갖습니다. 그러나 현재 사용중인 루틴의 다른 인스턴스를 호출하면 새 인스턴스에는 모든 관련 변수의 새로운 관련없는 사본이 있습니다. 효과적으로, 하나의 변수는 첫 번째 처리 레벨에서 하나의 값을 가질 수 있고 낮은 레벨에서 다른 값을 가질 수 있습니다.
이 기능은 많은 재귀 알고리즘이 작동하는 데 중요하므로 이러한 모든 값을 추적하는 호출 된 프레임 스택을 관리하지 않고 반복을 통해 재귀를 에뮬레이션 할 수 없습니다.
답변
X가 본질적으로 Y라고 말하는 것은 X를 표현한다는 (공식) 시스템을 염두에 둔 경우에만 의미가 있습니다. while람다 미적분학 의 의미를 정의하면 재귀 *를 언급 할 수 있습니다. 레지스터 머신으로 정의하면 아마 그렇지 않을 것입니다.
두 경우 모두 while 루프가 포함되어 있기 때문에 재귀 함수를 호출하면 사람들이 아마 당신을 이해하지 못할 것입니다.
* 아마도 간접적이지만, 예를 들어으로 정의한 경우 fold.
답변
이것은 귀하의 관점에 따라 다릅니다.
계산 성 이론 을 살펴보면 반복과 재귀는 똑같이 표현 적 입니다. 이것이 의미하는 것은 무언가를 계산하는 함수를 작성할 수 있으며, 재귀 적으로 또는 반복적으로 수행하는지 여부에 관계없이 두 가지 방법을 모두 선택할 수 있다는 것입니다. 재귀 적으로 계산할 수있는 것은 없으며 반복적으로 계산할 수 없으며 그 반대도 마찬가지입니다 (프로그램의 내부 작업은 다를 수 있음).
많은 프로그래밍 언어는 재귀와 반복을 동일하게 취급하지 않으며 정당한 이유가 있습니다. 일반적 으로 재귀는 언어 / 컴파일러가 호출 스택을 처리한다는 것을 의미하며 반복은 스택 처리를 직접 수행해야 할 수도 있음을 의미합니다.
그러나 루프 (for, while)와 같은 것은 실제로 재귀를위한 구문 설탕 일뿐이며 그런 식으로 무대 뒤에서 구현 되는 언어 , 특히 기능적 언어 가 있습니다. 함수형 언어에서는 종종 루핑이라는 개념이 없기 때문에 바람직하다.이를 추가하면 실질적인 이유 때문에 미적분학을 더 복잡하게 만들 수있다.
아니, 그들은 본질적으로 동일 하지 않습니다 . 그것들은 똑같이 표현 적입니다 . 즉, 반복적으로 계산할 수 없으며 반복적으로 계산할 수 없으며 반대의 경우도 마찬가지입니다. 그러나 일반적인 경우 (교회-튜링 논문에 따르면)에 관한 것입니다.
여기서는 재귀 프로그램 에 대해 이야기 하고 있습니다. 데이터 구조 (예 : 트리)와 같은 다른 형태의 재귀가 있습니다.
당신이에서 보면 보기의 구현 지점 , 다음 재귀와 반복이 거의 동일하지 않습니다. 재귀는 모든 호출에 대해 새 스택 프레임을 만듭니다. 재귀의 모든 단계는 자체 포함되어 있으며 수신자로부터 계산에 대한 인수를 얻습니다 (자체).
반면에 루프는 호출 프레임을 생성하지 않습니다. 이들을 위해 각 단계에서 컨텍스트가 유지되지 않습니다. 루프의 경우, 프로그램은 루프 조건이 실패 할 때까지 루프 시작으로 되돌아갑니다.
현실 세계에서 근본적인 차이를 만들 수 있기 때문에이 점을 알아야합니다. 재귀를 위해서는 모든 컨텍스트에서 전체 컨텍스트를 저장해야합니다. 반복을 위해 메모리에있는 변수와 저장 위치에 대한 정확한 제어가 가능합니다.
그런 식으로 보면 대부분의 언어에서 반복과 재귀가 근본적으로 다르고 다른 속성을 가지고 있음을 빨리 알 수 있습니다. 상황에 따라 일부 속성이 다른 속성보다 더 바람직합니다.
재귀는 프로그램을보다 간단하고 쉽게 테스트하고 증명할 수있게합니다 . 재귀를 반복으로 변환하면 일반적으로 코드가 더 복잡해져 실패 가능성이 높아집니다. 반면에 반복으로 변환하고 호출 스택 프레임의 양을 줄이면 필요한 메모리를 많이 절약 할 수 있습니다.
답변
차이점은 암시 적 스택과 의미입니다.
“마지막에 호출”하는 while 루프에는 완료시 다시 크롤링 할 스택이 없습니다. 마지막 반복은 종료되는 상태를 설정합니다.
그러나 이전의 작업 상태를 기억하는이 암시 적 스택이 없으면 재귀를 수행 할 수 없습니다.
스택에 명시 적으로 액세스하면 반복과 관련된 재귀 문제를 해결할 수 있다는 것은 사실입니다. 그러나 그렇게하는 것은 같지 않습니다.
의미 상 차이점은 재귀 코드를 보면 아이디어가 반복 코드와 완전히 다른 방식으로 전달된다는 사실과 관련이 있습니다. 반복 코드는 한 번에 한 단계 씩 작업을 수행합니다. 그것은 이전에 온 상태를 받아들이고 다음 상태를 만들기 위해서만 작동합니다.
재귀 코드는 문제를 프랙탈로 나눕니다. 이 작은 부분은 큰 부분처럼 보이므로이 부분과 그 부분을 같은 방식으로 수행 할 수 있습니다. 문제를 생각하는 다른 방법입니다. 매우 강력하고 익숙해집니다. 몇 줄로 많은 것을 말할 수 있습니다. 스택에 액세스 할 수 있다고해도 while 루프에서 벗어날 수는 없습니다.
답변
그것은 모두 당신이 본질적 으로 그 용어를 사용하는 것에 달려 있습니다 . 프로그래밍 언어 수준에서는 구문과 의미가 다르며 성능과 메모리 사용량이 상당히 다릅니다. 그러나 당신이 이론을 충분히 깊이 파고 들면 그것들은 서로의 관점에서 정의 될 수 있고, 따라서 어떤 이론적 의미에서 “동일”합니다.
진짜 질문은 : 반복 (루프)과 재귀를 구별하는 것이 언제 합리적이며, 그것을 같은 것으로 생각하는 것이 언제 유용합니까? 답은 실제로 수학적 증명을 작성하는 것과는 반대로 프로그래밍 할 때 반복과 재귀를 구별하는 것이 중요하다는 것입니다.
재귀는 새로운 스택 프레임, 즉 각 호출에 대한 새로운 로컬 변수 세트를 만듭니다. 오버 헤드가 발생하고 스택의 공간을 차지하므로 충분한 재귀가 스택을 오버플로하여 프로그램이 중단 될 수 있습니다. 반면에 반복은 기존 변수 만 수정하므로 일반적으로 더 빠르며 일정한 양의 메모리 만 차지합니다. 따라서 이것은 개발자에게 매우 중요한 차이점입니다!
꼬리 호출 재귀가있는 언어 (일반적으로 기능적인 언어)에서 컴파일러는 일정한 양의 메모리 만 차지하는 방식으로 재귀 호출을 최적화 할 수 있습니다. 이러한 언어에서 중요한 차이점은 반복 대 재귀가 아니라 비 꼬리 전화 재귀 버전의 꼬리 전화 재귀와 반복입니다.
결론 : 차이점을 말할 수 있어야합니다. 그렇지 않으면 프로그램이 중단됩니다.
답변
while루프는 재귀의 한 형태입니다. 예를 들어이 질문에 대한 대답을 참조하십시오 . 이들은 계산 이론에서 μ 연산자에 해당합니다 (예 : 여기 참조 ).
for숫자, 유한 컬렉션, 배열 등을 반복하는 모든 루프 변형은 기본 재귀에 해당합니다 (예 : here 및 here 참조) . 점을 유의 forC, C의 루프 ++, 자바, 등등, 사실에 대한 문법 설탕 있습니다 while루프, 따라서 그것을 대응 원시 재귀하지 않습니다. 파스칼 for루프는 원시 재귀의 예입니다.
중요한 차이점은 기본 재귀는 항상 종료되지만 일반 재귀 ( while루프)는 종료되지 않을 수 있다는 것입니다.
편집하다
의견 및 기타 답변에 대한 일부 설명. “물건 자체 또는 유형으로 정의 된 경우 재귀가 발생합니다.” ( wikipedia 참조 ). 그래서,
while 루프는 본질적으로 재귀입니까?
while자체 관점 에서 루프를 정의 할 수 있기 때문에
while p do c := if p then (c; while p do c))
다음 예 하는 while루프는 재귀의 한 형태이다. 재귀 함수는 또 다른 형태의 재귀입니다 (재귀 정의의 다른 예). 리스트와 트리는 다른 형태의 재귀입니다.
많은 답변과 의견에 의해 암시 적으로 가정되는 또 다른 질문은
while 루프와 재귀 함수는 동일합니까?
이 질문에 대한 답은 아니오입니다 . while루프는 꼬리 재귀 함수에 해당합니다. 루프에서 액세스하는 변수는 암시 적 재귀 함수의 인수에 해당하지만 다른 사람들이 지적했듯이 꼬리 비 재귀 함수 while추가 스택을 사용하지 않으면 루프 로 모델링 할 수 없습니다 .
따라서 ” while루프는 재귀의 형태”라는 사실이 “일부 재귀 함수는 while루프 로 표현할 수 없다는”사실과 모순되지 않습니다 .
답변
꼬리 호출 (또는 꼬리 재귀 호출이) 정확하게 (모든 밀어없이 “인수 고토 ‘로 구현 추가 온 전화 프레임 호출 스택 ) 일부 기능 언어 (OCaml의는 특히) 루프의 일반적인 방법입니다.
따라서 while 루프 (언어가있는 언어)는 본문 (또는 헤드 테스트)에 대한 꼬리 호출로 끝나는 것으로 볼 수 있습니다.
마찬가지로 일반 (비 꼬리 호출) 재귀 호출은 루프 (일부 스택 사용)로 시뮬레이션 할 수 있습니다.
연속 및 연속 전달 스타일에 대해서도 읽어보십시오 .
따라서 “재귀”와 “반복”은 상당히 동일합니다.