저는 MIPS의 초보자이고 (대학에서 MIPS 어셈블리를 배우기 시작하면서) MIPS에서 재귀 함수가 작동하는 방식을 이해하는 데 문제가 있습니다.
예를 들어, MIPS로 작성하기위한이 프로그램 (C)이 있습니다.
int fact (int n)
{
if (n < 1) return 0;
else return n * fact(n - 1);
}
누군가가 재귀 함수의이 또는 다른 예를 통해 나를 도와주고 어떻게 작동하는지 설명해 줄 수 있습니까?
내가 공유하고 싶은 첫 번째 것은 이것을 MIPS로 변환fact 하는 복잡성이 재귀가 관련되어 있기 때문이 아니라 단순한 함수 호출의 존재에서 비롯된다는 것 입니다. 재귀적인 것은 IMHO a red herring 입니다. 이를 위해 여러분이 언급 한 재귀 함수의 모든 복잡성을 가진 비 재귀 함수를 설명하겠습니다.
int fact (int n)
{
if (n < 1) return 0;
else return n * other(n - 1); // I've changed the call to "fact" to function "other"
}
내 변경은 더 이상 재귀 적이 지 않습니다! 그러나이 버전의 MIPS 코드는 귀하의 MIPS 코드와 동일하게 보입니다 fact(물론 jal fact변경 되는 경우는 예외입니다 jal other). 이것은 번역의 복잡성이 함수 내의 호출로 인한 것이며 호출되는 사람과는 아무 관련이 없음을 설명하기위한 것입니다. (최적화 기술이있는 YMMV이지만)
함수 호출을 이해하려면 다음을 이해해야합니다.
C에는 명시 적 매개 변수가 있습니다. 물론 이러한 명시 적 매개 변수는 어셈블리 / 기계 언어로도 나타납니다. 그러나 C 코드에서는 볼 수없는 기계 코드로 전달되는 매개 변수도 있습니다. 이것의 예로는 반환 주소 값과 스택 포인터가 있습니다.
여기에 필요한 것은 (재귀와 무관 한) 함수 분석입니다.
매개 변수 n는 $a0기능 입력에 있습니다. 의 값은 n함수 호출 (to other) 뒤에 필요합니다. 그 함수 호출이의 오른손 피연산자를 반환 할 때까지 곱할 수 없기 때문입니다 *.
따라서, n(왼쪽 피연산자에가 *)에 대한 함수 호출을 반드시 살아남 아야한다 other, 그리고 $a0그것은하지 않습니다 - 우리 자신의 코드의 용도를 변경하기 때문에 $a0호출 순서 other(n-1)로 n-1로 이동해야 $a0그것에 대해.
또한 (C에서 암시 적) 매개 변수 $ra는 호출자에게 반환하는 데 필요한 반환 주소 값을 보유합니다. other마찬가지로에 대한 호출 은 $ra레지스터의 용도를 변경하여 이전 값을 삭제합니다.
따라서이 함수 (사용자 또는 내)는 본문 내에있는 함수 호출 (예 :에 대한 호출 other) 에서 살아 남기 위해 두 개의 값이 필요합니다 .
해결책은 간단합니다. 필요한 값 (우리가하는 일에 의해 용도가 변경되거나 지워지거나 피 호출자가 잠재적으로 할 수있는 레지스터에 있음)을 다른 곳으로 이동하거나 복사해야합니다.
이를 위해 메모리를 사용할 수 있으며 스택을 사용하여 이러한 목적을위한 메모리를 얻을 수 있습니다.
이를 기반으로을 호출 한 후 필요한 두 가지 (그렇지 않으면 지워질 수 있음)를위한 공간이있는 스택 프레임을 만들어야합니다 other. 항목 $ra을 저장하고 나중에 다시로드해야 반환 할 수 있습니다. 또한 초기 n값을 저장해야 곱하기 위해 사용할 수 있습니다. (스택 프레임은 일반적으로 함수 프롤로그에서 생성되고 함수 에필로그에서 제거됩니다.)
기계 코드 (또는 일반적으로 프로그래밍)의 경우와 마찬가지로 요점은 동일하지만 다른 방법으로도 처리 할 수 있습니다. (이것은 좋은 일이며 최적화 컴파일러는 일반적으로 특정 상황에서 가장 좋은 방법을 찾습니다.)
재귀의 존재 또는 부재는이를 어셈블리 / 기계 언어로 변환하는 데 필요한 기본 분석을 변경하지 않습니다. 재귀는 스택 오버플로 가능성을 크게 증가 시키지만 그렇지 않으면이 분석을 변경하지 않습니다.
명확하게 말하면 재귀는 동적으로 확장 가능한 호출 스택을 사용해야한다는 요구 사항을 부과합니다. 모든 최신 컴퓨터 시스템은 호출을 위해 이러한 스택을 제공하므로이 요구 사항은 오늘날의 시스템에서 쉽게 잊거나 무시할 수 있습니다.
재귀가없는 프로그램의 경우 호출 스택이 필요하지 않습니다. 로컬 변수는 함수 전용 전역 변수 (반환 주소 포함)에 할당 될 수 있으며 이는 특정 기능을 제공하지 않는 PDP-8과 같은 특정 구형 시스템에서 수행되었습니다. 호출 스택에 대한 하드웨어 지원.
매개 변수를 전달하기 위해 스택 메모리를 사용하거나 레지스터가 좋지 않은 시스템은 변수가 중첩 된 함수 호출을 견디는 메모리에 이미 저장되어 있기 때문에이 답변에 설명 된 분석이 필요하지 않을 수 있습니다.
위의 분석에 대한 요구 사항을 생성하는 것은 레지스터가 풍부한 최신 기계에서 레지스터를 분할하는 것입니다. 이러한 레지스터가 풍부한 머신은 CPU 레지스터에서 매개 변수와 반환 값 (대부분)을 전달하므로 효율적이지만 레지스터가 한 기능에서 다른 기능으로 용도가 변경 될 때 복사본을 만들어야하는 경우가 있습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다