귀속 및 한 노 타 문 제 를 깊이 이해 하 다 [데이터 구조]

깊이 이해 하 다
1. 재 귀 란 무엇 인가?
재 귀 는 함수 가 직접적 이거 나 간접 적 으로 자신 을 호출 하 는 것 이다.
2. 함 수 는 어떻게 호출 을 완성 합 니까?
2.1 기조 함수 가 조 정 된 함 수 를 호출 하기 전에 세 가지 일 을 해 야 한다.
1. 기조 함 수 는 모든 실 참, 반환 주 소 를 조 정 된 함수 에 전달 합 니 다. 2. 조 정 된 함수 의 부분 변수 (형 삼 포함) 에 저장 공간 을 분배 합 니 다. 3. 조 정 된 함수 입구 로 제 어 를 옮 깁 니 다.
2.2 호출 함수 가 메 인 함수 로 되 돌아 가기 전에 세 가지 일 을 해 야 합 니 다.
1. 조 정 된 함수 의 액 반환 결 과 를 저장 합 니 다. 2. 조 정 된 함수 가 차지 하 는 공간 을 방출 합 니 다. 3. 조 정 된 함수 에 따라 저 장 된 반환 주소 에 따라 제어 권 을 메 인 함수 로 이전 합 니 다.
예 를 들 어 설명:

/**
    1.  main()     5,printf("hello
")            
    2. f() n        
    3.main()        f()  
*/
void main()
{
    f(5);
    printf("hello
");
}
/**
    1.          7    
    2.    n     
    3.         ，       main()   printf("hello
")     
*/
int f(int n)
{
    n=n+2;
    return n;
}

3. 귀속 만족 의 2 가지 조건
1. 명확 한 종료 조건 이 있어 야 합 니 다. 2. 이 함수 가 처리 하 는 문제 규 모 는 반드시 감소 해 야 합 니 다. (재 귀 문제 가 클 수록 해결 할 수 없습니다)
4. 재 귀 와 순환 의 관계
모든 순환 은 재 귀 로 이 루어 질 수 있 지만, 반대로 모든 재 귀 는 반드시 순환 으로 이 루어 질 수 있 는 것 은 아니다.
재 귀: 이해 하기 쉽 고 속도 가 느 립 니 다 (함수 간 의 호출, 시간 소모 가 필요 합 니 다). 공간 이 넓 습 니 다 (함수 간 의 호출, 공간 을 차지 해 야 합 니 다)
순환: 이해 하기 어렵 고 속도 가 빠 르 며 공간 을 차지 하 는 것 이 적다.
2. 곱 하기 문제 와 1 - 100 의 더하기 와 문 제 를 재 귀적 으로 해결 합 니 다.
1. 재 귀적 으로 계승 문 제 를 해결한다.
n 의 계단: n *!(n - 1) n - 1 의 계단: (n - 1) *!(n - 2) n - 2 의 계단: (n - 2) *!(n - 3).

#include 
#include 
//     
int mult(n)
{
    if(n==1)
    {
        return 1;
    }
    else
    {
        return n*mult(n-1);
    }
}
int main()
{
    int val=mult(3);
    printf("%d",val);
    return 0;
}

2. 재 귀적 으로 1 - 100 의 더하기 와 문 제 를 해결한다.
1 - 100 의 합: 100 + (1 - 99 의 합) 1 - 99 의 합: 99 + (1 - 98 의 합) 1 - 98 의 합: 98 + (1 - 97 의 합)... 1 의 합: 1

#include 
#include 
//          
int mult(n)
{
    if(n==1)
    {
        return 1;
    }
    else
    {
        return n+mult(n-1);
    }
}
int main()
{
    int val=mult(100);
    printf("%d",val);
    return 0;
}

3. 한 노 타 문제
한 노 타의 전설 은 자세히 말 하지 않 겠 습 니 다. 들 어보 지 못 한 것 은 여 기 를 클릭 하 세 요: 한 노 타
재 귀적 인 사상 으로 한 노 타 문 제 를 해결한다. 1. 문 제 를 원자 절차 로 분해한다. 예 를 들 어 접시 가 2 개 밖 에 없 을 때 어떻게 해 야 하 는가. 2. 재 귀적 인 출구 를 찾는다 (접시 가 1 개 밖 에 없 을 때 C 기둥 으로 직접 이동한다)

#include 
#include 
//       （     2   ，3   ）
void Hanoi(int n,char A,char B,char C)
{
    // A   1      ， A     C 
    if(n==1)
    {
        printf("   %d    %c   %c 
",n,A,C);
    }
    else
    {
        //    2    A   C     B 
        Hanoi(n-1,A,C,B);
        //    1    A    C 
        printf("   %d    %c   %c 
",n,A,C);
        //  2    B   A   C 
        Hanoi(n-1,B,A,C);
    }
}
int main()
{
    Hanoi(3,'A','B','C');
    return 0;
}

정리
재 귀 사상 으로 문 제 를 처리 합 니 다. 1. 우선 우 리 는 문제 의 모든 단 계 를 분해 하고 원자 로 나 누 는 절차 2. 우 리 는 작 성 된 재 귀 함수 가 어떻게 실현 되 는 지 에 관심 을 가 질 필요 가 없습니다. 왜냐하면 우 리 는 원자 절차 로 분해 하고 재 귀 처리 할 때 그 자체 가 실현 되 기 때 문 입 니 다. 3. 재 귀 의 실질 은 n 규모 의 문 제 를 n - 1 규모 의 문제 로 전환 하 는 것 입 니 다. n - 1 의 문 제 는 n - 1 의 문제 로 전환 하 는 것 입 니 다.n - 2 규모 의 문 제 를 해결 할 수 있 는 규모 의 문제 로 전환한다.