C 언어 함수의 귀속과 호출 실례 분석

1. 기본 내용:
C 언어의 함수는 귀속적으로 호출할 수 있다. 즉, 직접 (단순 귀속) 또는 간접 (간접 귀속) 으로 스스로 자신을 조정할 수 있다.요점: 1. C 언어 함수는 반복적으로 호출할 수 있다.2. 직접 또는 간접적으로 두 가지 방식으로 호출할 수 있다.현재는 직접 귀속 호출만 논의하고 있다.
귀속 조건
귀속 방법을 채택하여 문제를 해결하려면 반드시 다음과 같은 세 가지 조건에 부합해야 한다. 1. 해결해야 할 문제를 새로운 문제로 전환시킬 수 있다. 그러나 이 새로운 문제의 해결 방법은 여전히 원래의 해결 방법과 같고 처리하는 대상은 규칙적으로 증가하거나 감소할 뿐이다.설명: 문제를 해결하는 방법이 같고 함수를 호출하는 매개 변수가 매번 다르기 때문에 (규칙적으로 증가하거나 감소) 규칙이 없으면 귀속 호출을 적용할 수 없다.2. 이 전환 과정을 응용하여 문제를 해결할 수 있다.설명: 다른 방법을 사용하면 비교적 번거롭거나 해결하기 어려우며, 귀속적인 방법을 사용하면 문제를 잘 해결할 수 있다.3. 반드시 명확한 귀속을 끝내는 조건이 있어야 한다.설명: 반드시 적당한 곳에서 귀속 호출을 끝낼 수 있어야 한다.그렇지 않으면 시스템이 붕괴될 수도 있다.
3. 실례를 귀속시킨다
예: 돌아가는 방법으로 n을 구해라!n>1시, n을 구하세요!의 질문을 n*(n-1)로 바꿀 수 있습니다!라는 새로운 질문을 던졌다.예를 들어 n=5: 제1부분: 5*4*3*2*1n*(n-1)!제2부분: 4*3*2*1(n-1)*(n-2)!제3부분: 3*2*1(n-2)(n-3)!네 번째 부분: 2*1(n-3)(n-4)!제5부분: 1(n-5)!5-5=0, 획득치 1, 귀속 종료.소스 프로그램:

 
  
　　fac(int n) 
  
　　{int t; 
  
　　if(n==1)||(n==0) return 1; 
  
　　else 
  
　　{ t=n*fac(n-1); 
  
　　return t; 
  
　　} 
  
　　} 
  
　　main( ) 
  
　　{int m,y; 
  
　　printf(“Enter m:”); 
  
　　scanf(“%d”,&m); 
  
　　if(m<0) printf(“Input data Error!
”); 
  
　　else 
  
　　{y=fac(m); 
  
　　printf(“
%d! =%d 
”,m,y); 
  
　　} 
  
　　} 
  
 
 

4. 귀속 설명
1. 함수가 스스로 자신을 호출할 때 시스템은 자동으로 함수에 있는 현재의 변수와 인삼을 잠시 보존한다. 새로운 호출 과정에서 시스템은 새로 호출된 함수에 사용되는 변수와 인삼을 위해 다른 저장 단원(메모리 공간)을 개척한다.매번 호출 함수에 사용되는 변수는 서로 다른 메모리 공간에 있습니다.2. 귀속 호출의 차원이 많을수록 동명 변수가 차지하는 저장 단원도 많아진다.매번 함수가 호출될 때마다 시스템은 이 함수의 변수를 위해 새로운 메모리 공간을 개척한다는 것을 반드시 기억해야 한다.3. 이번 호출의 함수 운행이 끝날 때 시스템은 이번 호출에 사용된 메모리 공간을 방출한다.프로그램의 프로세스는 이전 층의 호출점으로 되돌아와 처음에 이 층에 들어갔을 때 함수의 변수와 인삼이 차지하는 메모리 공간의 데이터를 얻는다.4. 모든 귀속 문제는 비귀속 방법으로 해결할 수 있지만 비교적 복잡한 귀속 문제에 대해 비귀속 방법으로 프로그램을 매우 복잡하고 이해하기 어렵게 만든다. 함수의 귀속 호출은 이런 문제를 해결할 때 프로그램이 간단명료하고 읽기 쉽다.그러나 귀속 호출 과정에서 시스템은 각 층의 호출 중의 변수를 위해 메모리 공간을 개척하고 각 층의 호출 후의 귀환점을 기억하며 많은 추가 비용을 증가해야 하기 때문에 함수의 귀속 호출은 보통 프로그램의 운행 효율을 떨어뜨릴 수 있다.
5. 절차

 
  
　　fac(int n) /* */ 
  
　　{ int t; /* t */ 
  
　　if(n==1)||(n==0) /* 1 */ 
  
　　return 1; 
  
　　else 
  
　　{ t=n*fac(n-1); /* n-1 , */ 
  
　　return t; /* 。*/ 
  
　　} 
  
　　} 
  
 
 

하나의 함수가 그 함수 체내에서 호출되면 그 자체를 귀속 호출이라고 부른다.이런 함수를 귀속 함수라고 부른다.C 언어는 함수의 귀속 호출을 허용합니다.귀속 호출에서 주조 함수는 또 피조 함수이다.실행 귀속 함수는 자신을 반복적으로 호출하여 호출할 때마다 새로운 층으로 들어갑니다.예를 들어 다음과 같은 함수 f가 있습니다.

 
  
    int f(int x) 
  
    { 
  
      int y; 
  
      z=f(y); 
  
      return z; 
  
    } 
  
 
 

이 함수는 귀속 함수다.그러나 이 함수를 실행하면 끊임없이 자신을 호출하는 것은 옳지 않다.귀속 호출이 중지 없이 진행되는 것을 방지하기 위해서는 함수 내에 귀속 호출을 중지하는 수단이 있어야 한다.상용하는 방법은 조건 판단을 가하여 어떤 조건을 만족시킨 후에는 다시 귀속 호출을 하지 않고 층층이 되돌아오는 것이다.다음은 귀속 호출의 집행 과정을 예를 들어 설명한다.
[예8.5] 귀속법으로 n을 계산한다!
역귀법으로 n을 계산해라!다음 방정식으로 n!=1         (n=0,1)    n×(n-1)!(n>1) 공식에 따라 다음과 같이 프로그래밍할 수 있다. long ff(int n) {long f;if(n<0) printf('n<0, input error');else if(n==0||n=1) f=1;else f=ff(n-1)*n;return(f);
main(){    int n;    long y;    printf("input a inteager number:");    scanf("%d",&n);    y=ff(n);    printf("%d!=%ld",n,y);}
프로그램에서 제시한 함수 ff는 귀속 함수입니다.주함수 ff를 호출하면 함수 ff 실행에 들어갑니다. n<0, n=0 또는 n=1일 경우 함수의 실행을 종료합니다. 그렇지 않으면 ff 함수 자체를 호출합니다.매번 귀속 호출의 실참이 n-1이기 때문에 n-1의 값을 형삼 n에 부여하고 마지막에 n-1의 값이 1일 때 다시 귀속 호출을 한다. 형삼 n의 값도 1이기 때문에 귀속이 중지된다.그리고 층층이 되돌아갈 수 있다.
다음에 우리는 다시 예를 들어 이 과정을 설명한다.이 프로그램을 실행할 때 5를 입력하면 5를 구합니다.주함수 중의 호출문은 y=ff(5)이고 ff함수에 들어간 후 n=5는 0 또는 1과 같지 않기 때문에 f=ff(n-1)*n, 즉 f=ff(5-1)*5를 실행해야 한다.이 문장은 ff를 귀속 호출하면 ff(4)이다.
네 차례의 컴포지팅 호출을 한 후 ff 함수형이 얻은 값이 1이 되므로 컴포지팅 호출을 계속하지 않고 주조 함수를 층층이 되돌려주기 시작한다.ff(1)의 함수 반환값은 1, ff(2)의 반환값은 1*2=2, ff(3)의 반환값은 2*3=6, ff(4)의 반환값은 6*4=24, 마지막 반환값 ff(5)는 24*5=120이다.
예8.5도 귀속적인 방법으로 완성하지 않아도 된다.만약 추이법을 사용할 수 있다면, 즉 1부터 2를 곱하고, 다시 3을 곱하면... n까지 된다.추이법은 귀속법보다 이해와 실현이 쉽다.그러나 일부 문제는 귀속 알고리즘으로만 가능하다.대표적인 문제는 하나타워 문제다.
【예8.6】한오타워 문제는 한 판에 세 개의 바늘이 있는데 A, B, C이다.A바늘에는 크기가 같지 않은 64개의 원반이 씌워져 있는데 큰 것은 아래에 있고 작은 것은 위에 있다.그림5.4와 같다.이 64개의 원반을 A바늘에서 C바늘로 이동하려면 매번 한 개의 원반만 이동할 수 있고 이동은 B바늘로 할 수 있다.그러나 언제든지 바늘 위의 원반은 밑에 있고 작은 원반은 위에 있어야 한다.이동하려면
이 문제의 알고리즘 분석은 다음과 같다. A에 n개의 접시가 설치되어 있다.
n=1이면 디스크가 A에서 C로 바로 이동합니다.
만약 n=2라면:1.A의 n-1 (1) 개의 원반을 B로 옮기기;      2.A의 원반을 C로 옮기기;      3.마지막으로 B의 n-1 (1) 개의 원반을 C 위로 옮깁니다.
만약 n=3이라면: A. A의 n-1(2와 같으면 n`) 원반을 B(C의 도움을 빌린다)로 옮긴다. 절차는 다음과 같다. (1) A의 n`-1(1과 같다) 원반을 C로 옮긴다.(2) A의 원반을 B로 옮긴다.(3) C의 n`-1(1과 같음) 디스크를 B로 옮깁니다.B. A의 디스크 중 하나를 C로 이동합니다.C. B의 n-1(2와 같으면 n`으로 한다)개의 원반을 C(A의 도움을 빌린다)로 옮긴다. 단계는 다음과 같다. (1) B의 n`-1(1과 같다)개의 원반을 A로 옮긴다.(2) B의 접시를 C로 옮긴다.(3) A의 n`-1(1과 같음) 디스크를 C로 옮깁니다.
이제 세 개의 디스크가 이동합니다.
위의 분석을 통해 알 수 있듯이 n이 2보다 크면 이동하는 과정은 세 가지 절차로 분해될 수 있다. 첫 번째 단계는 A의 n-1개의 원반을 B로 옮기는 것이다.두 번째 단계는 A의 원반을 C로 옮기기;세 번째 단계는 B의 n-1개의 원반을 C로 옮기기;그중 첫 번째 단계와 세 번째 단계는 유사하다.
n=3시, 첫 번째 단계와 세 번째 단계는 같은 세 단계로 분해된다. 즉, n`-1개의 원반을 한 바늘에서 다른 바늘로 옮기고, 이곳의 n`=n-1.분명히 이것은 귀속 과정이다. 이 알고리즘에 따라 다음과 같이 프로그래밍할 수 있다. move(int n, int x, int y, int z) {if(n==1) printf('%c-->%c', x,z), else {move(n-1, x,z, y), printf('%c-->%c', x,z), move(n-1, y,z),    }}main(){    int h;    printf("input number:");    scanf("%d",&h);    printf("the step to moving %2d diskes:",h);    move(h,'a','b','c');}
프로그램에서 볼 수 있듯이 모브 함수는 하나의 귀속 함수로 네 개의 형삼 n, x, y,z가 있다.n은 원반의 수를 나타내고 x, y,z는 각각 세 개의 바늘을 나타낸다.move 함수의 기능은 x의 n개의 원반을 z로 이동하는 것이다.n==1일 때 x의 원반을 z로 옮겨 x→z를 출력한다.여n!1은 3단계로 나뉜다. 모브 함수를 호출하여 n-1개의 원반을 x에서 y로 옮긴다.x→z 출력하기;move 함수를 호출하여 n-1개의 원반을 y에서 z로 옮깁니다.귀속 호출 과정 중 n=n-1이기 때문에 n의 값은 차례로 줄어들고 마지막 n=1일 때 귀속을 중지하고 층층이 귀환한다.n=4시 프로그램이 실행된 결과: input number: 4 the step to moving 4 diskes: a→b a→c b→c a→c a→b c→b a→b a→b a→c c→a b→c a→c a→b a→b a→c b→c b→c