C 언어 프로그램 에서 재 귀 알고리즘 을 사용 하 는 인 스 턴 스 튜 토리 얼

1.문제:계산 n!
수학 적 계산 공식 은 다음 과 같다.

n！=n×(n-1)×(n-2)……2×1

재 귀적 인 방식 을 사용 하면 다음 과 같이 정의 할 수 있 습 니 다.

재 귀적 으로 계산 4!

F(4)=4×F(3)　　　　　　　　　　　　    

F(3)=3×F(2)

F(2)=2×F(1)

F(1)=1　　    

F(2)=(2)×(1)　　　     

F(3)=(3)×(2)

F(4)=(4)×(6)

24　　　　　　　　　　　　　　　　     

재 귀 방식 으로 계승 함수 의 실현 을 실현 합 니 다.

int fact(int n) {
  if(n < 0)
    return 0;
  else if (n == 0 || n == 1)
    return 1;
  else
    return n * fact(n - 1);
}

2.원리
다음은 재 귀적 인 작업 원 리 를 상세 하 게 분석 하 겠 습 니 다.
먼저 C 언어 에서 함수 의 실행 방식 을 살 펴 보고 C 프로그램 이 메모리 에 있 는 조직 방식 에 대해 알 아야 합 니 다.
쌓 인 성장 방향 은 낮은 주소 에서 높 은 주소 로 올 라 가 는 것 이 고 스 택 의 성장 방향 은 정반 대 입 니 다(실제 상황 은 CPU 의 시스템 구조 와 관련 이 있 습 니 다).
C 프로그램 에서 함 수 를 호출 했 을 때 스 택 에 서 는 이 호출 과 관련 된 정 보 를 저장 할 공간 을 배정 하고 모든 호출 이 활성 화 된 것 으로 여 겨 집 니 다.스 택 에 있 는 저장 공간 을 활성 기록 이나 스 택 프레임 이 라 고 합 니 다.
스 택 프레임 은 5 개 영역 으로 구성 되 어 있 습 니 다.입력 매개 변수,반환 값 공간,표현 식 을 계산 할 때 사용 하 는 임시 저장 공간,함수 호출 시 저 장 된 상태 정보 와 출력 매개 변 수 는 다음 그림 을 참조 하 십시오.

다음 프로그램 을 사용 하여 검사 할 수 있 습 니 다:

#include <stdio.h>
int g1=0, g2=0, g3=0;
int max(int i)
{
  int m1 = 0, m2, m3 = 0, *p_max;
  static n1_max = 0, n2_max, n3_max = 0;
  p_max = (int*)malloc(10);
  printf("  max    
");
  printf("in max: 0x%08x

",max);
  printf("  max      
");
  printf("in max: 0x%08x

",&i);
  printf("  max         
");
  printf("0x%08x
",&n1_max); 
//            
  printf("0x%08x
",&n2_max);
  printf("0x%08x

",&n3_max);
  printf("  max         
");
  printf("0x%08x
",&m1); 
//            
  printf("0x%08x
",&m2);
  printf("0x%08x

",&m3);
  printf("  max   malloc    
");
  printf("0x%08x

",p_max); 
//            
  if(i) return 1;
  else return 0;
}
int main(int argc, char **argv)
{
  static int s1=0, s2, s3=0;
  int v1=0, v2, v3=0;
  int *p;  
  p = (int*)malloc(10);
  printf("       (    )     
");
  printf("0x%08x
",&g1); 
//            
  printf("0x%08x
",&g2);
  printf("0x%08x

",&g3);
  printf("======================
");
  printf("        main  
");
  printf("main: 0x%08x

", main);
  printf("      
");
  printf("argv: 0x%08x

",argv);
  printf("            
");
  printf("0x%08x
",&s1); 
//            
  printf("0x%08x
",&s2);
  printf("0x%08x

",&s3);
  printf("            
");
  printf("0x%08x
",&v1); 
//            
  printf("0x%08x
",&v2);
  printf("0x%08x

",&v3);
  printf("  malloc      
");
  printf("malloc: 0x%08x

",p);
  printf("======================
");
  max(v1);
  printf("======================
");
  printf("         
");
  printf("max: 0x%08x

",max);
  return 0;
}

스 택 은 함수 호출 정 보 를 저장 하 는 절 호의 방안 이지 만 스 택 에 도 단점 이 있 습 니 다.
스 택 은 모든 함수 호출 정 보 를 함수 가 돌아 온 후에 야 방출 합 니 다.이것 은 상당히 큰 공간 을 차지 해 야 합 니 다.특히 프로그램 에서 많은 재 귀적 호출 을 사용 한 상황 에서.이외에 도 저장 과 복구 가 필요 한 정보 가 많아 활성 기록 을 생 성·폐기 하 는 데 시간 이 걸 릴 것 으로 보인다.우 리 는 교체 방안 을 채택 하 는 것 을 고려 해 야 한다.다행히도 우 리 는 앞에서 언급 한 이러한 단점 을 피하 기 위해 꼬리 귀속 이 라 고 불 리 는 특수 귀속 방식 을 채택 할 수 있다.
3.피 보 나치 수열

#include <stdio.h> 
 
int fibonacci(int a){//fibonacci  ，     1；             
  if (a == 1 || a == 2) 
  { 
    return 1; 
  }else{ 
    return fibonacci(a - 1) + fibonacci(a - 2); 
  } 
} 
 
void main(){ 
  printf("%d
",fibonacci(40)); 
} 

 
4.재 귀적 으로 성형 숫자 를 문자열 로 변환

#include <stdio.h> 
 
int toString(int i, char str[]){//              
  int j = 0; 
  char c = i % 10 + '0'; 
  if (i /= 10) 
  { 
    j = toString(i, str) + 1; 
  } 
  str[j] = c; 
  str[j + 1] = '\0'; 
  return j; 
} 
 
void main(){ 
  char str[100]; 
  int i; 
  printf("enter a integer:
"); 
  scanf("%d",&i); 
  toString(i,str); 
  puts(str); 
} 

5.한 노 타

#include <stdio.h> 
 
void hanoi(int i,char x,char y,char z){ 
  if(i == 1){ 
    printf("%c -> %c
",x,z); 
  }else{ 
    hanoi(i - 1,x,z,y); 
    printf("%c -> %c
",x,z); 
    hanoi(i - 1,y,x,z); 
  } 
} 
 
void main(){ 
  hanoi(10,'A','B','C'); 
} 

 
6.네 개의 숫자 를 최대 로 찾 아 라

int max(int a, int b, int c, int d){ 
  if(a > b && a > c && a > d){ 
    return a; 
  }else{ 
    max(b,c,d,a); 
  } 
} 

7.원숭이 가 복숭아 를 먹는다
매일 반 만 먹고 하 나 를 더 먹고 10 일 째 먹고 싶 을 때 하나 밖 에 남지 않 았 습 니 다.모두 얼마 인지 물 어보 세 요.

int chitao(int i){//    ，          ，            
  if(i == 10){ 
    return 1; 
  }else{ 
    return (chitao(i + 1) + 1) * 2; 
  } 
}