재귀는 실제로 무엇이며이 프로그램의 출력을 설명합니까?

Question

정말이 코드를 이해할 수 없습니다. 함수가 실제로 스스로를 호출 할 때? 그것은 스택의 개념과 관련이 있습니다. 그러나 저는 여전히 이러한 질문을 해결할 수 없습니다.

#include<stdio.h> 

fun(int); 

main() 
{ 
    int x=3; 
    fun(x); 
} 

fun(int a) 
{ 
    if(a<0) 
    { 
    fun(--a); // what happens when function calls itself 
    printf("%d",a); 
    fun(--a); 
    } 
} 

이 기간 동안 발생한 일련의 사건을 설명하십시오.

Answer 1

함수는 메모리의 어딘가에있는 코드 일뿐입니다. 함수 호출을 할 때마다 컴파일러는 함수 호출이 완료된 후 실행될 다음 명령의 주소를 저장하는 플랫폼의 어셈블리 코드 명령으로 변환하고 메모리에서 말 그대로 "점프"할 위치를 프로세서에 알려줍니다 실행될 다음 명령을 읽습니다.

재귀는 메모리에서 함수의 코드 블록 시작 부분으로 프로세서가 쉽게 "건너 뛰게"할 수 있기 때문에 효과적입니다. 현재 호출하는 현재 함수는 다른 함수와 마찬가지로 메모리 주소를 가지므로 프로세서가 메모리의 현재 함수 코드 블록 또는 메모리의 다른 함수 코드 블록의 시작 부분으로 점프하지 않아도됩니다.

스택은 현재 함수의 인수와 자동 변수를 저장할 위치뿐만 아니라 함수 호출을 완료 한 후에 명령이 실행되도록 반환 주소를 저장해야하기 때문에 작동합니다. 따라서 연속적인 함수 호출을 할 때 스택이 아래쪽으로 커지면 이전에 호출 된 함수에 대한 리턴 주소뿐만 아니라 인수와 함께 생성 된 call-stack이 스택 상에 있습니다. 이것을 집합 적으로 함수의 "스택 프레임"이라고합니다. 함수에서 돌아 오면 현재 함수의 스택 프레임이 스택 맨 아래에서 팝되고 함수가 완료된 후 프로세서가 다시 점프해야하는 메모리 주소를 읽고 실행합니다. 재귀의 경우 이것은 동일한 함수의 이전 버전으로 간단히 돌아가지만,이 경우 자동 스택 변수와 인수는 이전의 스택 프레임으로 돌아 왔으므로 반환 된 후에 달라집니다. 함수의 버전.

Answer 2

함수 인수는 C로 값에 의해 전달됩니다. 즉, 함수를 호출 할 때마다 임시 로컬 변수가 만들어집니다. 함수가 재귀 적으로 호출되면 매번 새로운 변수 집합이 만들어집니다. 그러나 재귀가 저장 공간을 절약 할 필요는 없습니다. 처리중인 값의 스택을 유지해야하기 때문입니다.

Answer 3

이 경우, fun()를 호출하는 것은 다른 함수를 호출하는 것과 같습니다. 예를 들어 :

int main() { 
    int a = 0; 
    foo(a); 
    printf("main a = %d\n", a); 
} 

void foo(int a) { 
    a = 1; 
    bar(a); 
    printf("foo a = %d\n", a); 
} 

void bar(int a) { 
    a = 2; 
    printf("bar a = %d\n", a); 
} 

귀하의 호출 순서 다음과 같이 :

bar a = 2 
foo a = 1 
main a = 0 

인수는 값에 의해 전달되는, 그래서 a복사 :

main(); 
foo(); 
bar(); 

그리고 당신의 출력이 될 것입니다이고 실제로 각 기능의 다른 변수입니다. 재귀에서도 마찬가지입니다.

main(); x = 3 
fun(3); a = 3, so a > 0, nothing happens, return to main() 

당신은 재미() 자신을 호출 있도록> 0

main(); x = 3 
fun(3); a = 3, a > 0 so --a = 2, fun(2) 
fun(2); a = 2, a > 0 so --a = 1, fun(1) 
fun(1); a = 1, a > 0 so --a = 0, fun(0) 
fun(0); a = 0, so return to fun(1) 

fun(1); printf("%d", a) displays 1, --a = 0, fun(0) /* same as fun(1) above */ 
fun(0); a = 0, so return to fun(1) 

fun(1); nothing left to do so return to fun(2)  /* same as fun(1) above */ 

fun(2); printf("%d", a) displays 2, --a = 1, fun(1) 
fun(1); a = 1, a > 0 so --a = 0, fun(0)    /* this is a new fun(1) */ 
fun(0); a = 0, so return to fun(1) 

fun(1); printf("%d", a) displays 1, --a = 0, fun(0) 
fun(0); a = 0, so return to fun(1) 

fun(1); nothing left to do so return to fun(2) 

fun(2); nothing left to do so return to fun(3) 

fun(3); printf("%d", a) displays 3, --a = 2, fun(2) /* halfway point */ 
fun(2); a = 2, a > 0 so --a = 1, fun(1) 
fun(1); a = 1, a > 0 so --a = 0, fun(0) 
fun(0); a = 0, so return to fun(1) 

fun(1); printf("%d", a) displays 1, --a = 0, fun(0) 
fun(0); a = 0, so return to fun(1) 

fun(1); nothing left to do so return to fun(2) 

fun(2); printf("%d", a) displays 2, --a = 1, fun(1) 
fun(1); a = 1, a > 0 so --a = 0, fun(0) 
fun(0); a = 0, so return to fun(1) 

fun(1); printf("%d", a) displays 1, --a = 0, fun(0) 
fun(0); a = 0, so return to fun(1) 

fun(1); nothing left to do so return to fun(2) 

fun(2); nothing left to do so return to fun(3) 

fun(3); nothing left to do so return to main() 

을 (위에서 아래로 읽기) 그리고 당신의 출력해야 할 때 조건을 변경했다 경우의 트리 구조를 반영 1,213,121을 전화 :

 3 
    /\ 
    / \ 
    2  2 
    /\ /\ 
    1 1 1 1