귀속과 귀속 함수

귀속: C 언어 프로그래밍에서 복잡한 문제를 분석하는 중요한 사상이다.귀속 함수: 한 함수의 함수체에서 이 함수 자체를 직접 또는 간접적으로 호출한 것을 가리킨다.
 

역귀함수 실행 과정

점차적 단계: 원래의 문제에서 출발하여 점차적 공식에 따라 미지의 점차적 점차적 점차적 점차적 점차적 점차적 점차적 점차적 점차적 점차적 점차적 점차적 점차적 점차적 점차적 점차적 점차적 점차적 점차적 점차
회귀 단계: 귀속 종지 조건에 따라 결과를 구하고 역방향으로 귀속 공식을 대입하여 원래 문제의 해답을 구한다.
 

구조 귀속 함수의 관건

귀속 공식: 귀속 공식은 일종의 추이 공식에 속한다.종료 조건: 추이 공식은 자신을 무제한으로 호출할 수 없으며 이런 출구가 필요하다.
 

대표적인 사례

 

문제1: n!

문제 분석
 

n! = n * (n-1)!   
(n-1)! = (n-1) * (n-2)!
(n-2)! = (n-2) * (n-3)!
......
......
2! = 2 * 1!

1. 점차적인 공식은 분명히 n!=n * (n-1)!점차적인 공식으로 (n-1)!동일한 법칙의 분해를 진행하다.
2. 종료 조건 1!=1, 이것은 이미 알고 있는 것이다.
 
함수 프로그래밍

#include 
int fac(int n) 
{
        if (n == 0 || n == 1)
                return 1;

        return n * fac(n-1);
}

 
 
질문 2: 피보나치 수열 계산

1, 1, 2, 3, 5, 8, 13, 21, 34, 55......

1. 법칙: 이 수열은 3항부터 시작하여 각 항은 앞의 두 항의 합과 같다.
2. 추이 공식: f(n) = f(n-1) + f(n-2)
3. 종료 조건: f(1)=1, f(2)=1
 
함수 프로그래밍

int fib(int n) 
{
        if (n == 1 || n == 2)
                return 1;

        return fib(n-1)+fib(n-2);
}