C 의 귀속 함수 (41)

우 리 는 오늘 하 재 귀, 재 귀 는 수학 적 으로 나 누 어 자치 적 인 사상 이다.재 귀 는 경계 조건 이 필요 하 다. 경계 조건 이 만족 하지 않 을 때 재 귀 는 계속 진행 된다.경계 조건 이 만족 할 때 귀속 은 정지한다.재 귀 는 대형 복잡 문 제 를 원래 문제 와 같 지만 규모 가 작은 문제 로 전환 시 켜 처리 하 는 것 이다.
        함수 체 내 부 는 자신 을 호출 할 수 있 습 니 다. 함수 체 에는 자기 호출 함수 가 존재 합 니 다.재 귀 함 수 는 재 귀 하 는 수학 사상 이 프로그램 디자인 에서 의 응용 으로 재 귀 함 수 는 반드시 출구 가 있어 야 하고 함수 의 무한 재 귀 는 프로그램 스 택 이 넘 쳐 서 무 너 질 것 이다.재 귀 모델 은 저희 가 보통 아래 와 같이 표시 합 니 다.
        우 리 는 다음 에 재 귀적 인 방법 으로 함수 로 문자열 의 길 이 를 구 합 니 다. 사상 은 바로 아래 와 같 습 니 다.
        구체 적 인 코드 는 다음 과 같다.

#include 

int strlen_r(const char* s)
{
    if( *s )
    {
        return 1 + strlen_r(s+1);
    }
    else
    {
        return 0;
    }
}

int main()
{
    printf("%d
", strlen_r("abc"));
    printf("%d
", strlen_r(""));
    
    return 0;
}

        컴 파일 결 과 를 봅 시다.
        결 과 는 우리 가 생각 한 대로 되 었 다.다음은 재 귀적 으로 피 폴 라 치 수열 을 어떻게 실현 하 는 지 살 펴 보 자. 1, 1, 2, 3, 5, 8, 13, 21........................................................
        프로그램 이 어떤 지 한번 봅 시다.

#include 

int fac(int n)
{
    if( n == 1 )
    {
        return 1;
    }
    else if( n == 2 )
    {
        return 1;
    }
    else
    {
        return fac(n-1) + fac(n-2);
    }
    
    return -1;
}

int main()
{
    printf("%d
", fac(1));
    printf("%d
", fac(2));
    printf("%d
", fac(9));
    
    return 0;
}

        앞의 두 개가 틀림없이 인쇄 된 것 은 모두 1 이 고, 세 번 째 가 인쇄 된 것 은 34 이다.컴 파일 결 과 를 살 펴 보 겠 습 니 다.
        우 리 는 내 려 와 서 한 노 타 문제 에 귀 속 된 응용 을 살 펴 보 자. 다음 과 같이 나 무 를 B 기둥 을 빌려 A 기둥 에서 C 기둥 으로 이동한다.매번 나무 조각 하나만 움 직 일 수 있다.작은 나무토막 만 큰 나무토막 위 에 나타 날 수 있다.
        우 리 는 이 문 제 를 분해 하여 n - 1 개의 나무토막 을 C 기둥 을 빌려 A 기둥 에서 B 기둥 으로 이동한다.맨 밑 에 있 는 유일한 나무토막 을 C 기둥 으로 직접 이동 하기;n - 1 개의 나 무 를 A 기둥 을 빌려 B 기둥 에서 C 기둥 으로 이동한다.프로그램 이 어떻게 실현 되 는 지 봅 시다.

#include 

int han_move(int n, char a, char b, char c)
{
    if( n == 1 )
    {
        printf("%c ==> %c
", a, c);
    }
    else
    {
        han_move(n-1, a, c, b);
        han_move(1, a, b, c);
        han_move(n-1, b, a, c);
    }
}

int main()
{
    han_move(3, 'A', 'B', 'C');
    
    return 0;
}

        컴 파일 결 과 를 봅 시다.
        우 리 는 이미 이 문제 의 해법 을 정확하게 실현 한 것 을 보 았 다.재 귀 에 대한 학습 을 통 해 다음 과 같이 요약 한다. 1. 재 귀 는 문 제 를 자치 적 으로 나 누 는 사상 이다.2. 재 귀 로 문 제 를 해결 하려 면 먼저 재 귀 모델 을 구축 해 야 한다.3. 재 귀 해법 은 반드시 경계 조건 이 있어 야 합 니 다. 그렇지 않 으 면 풀 리 지 않 습 니 다!
        모두 함께 C 언어 를 공부 하 러 오신 것 을 환영 합 니 다. 저 에 게 QQ: 243343083 을 추가 할 수 있 습 니 다.