[데이터 구조 와 알고리즘] 재 귀 와 교체 의 통용 전환 사상 에 깊이 들 어가 기 쉽다.

재 귀 와 교체 의 통용 전환 사상 을 깊이 파고 들 었 다.
일반적으로 교체 할 수 있 는 곳 은 재 귀 를 사용 하지 마라!이론 적 으로 말 하면 모든 재 귀 와 교체 간 에 서로 전환 할 수 있다!
문 제 를 푸 는 것 이 [하루 에 하나의 LeetCode] \ # 130. Surrounded Regions 에 부 딪 혔 습 니 다. 그래서 재 귀 와 교 체 를 정리 하 겠 습 니 다.
(1) 무엇이 교체 입 니까?
우선 아래 의 간단 한 코드 를 살 펴 보 겠 습 니 다.

int sum(int n )
{
    int sum =0;
    for(int i = 1 ; i <= n;i++) sum+=n;//  1~n  
    return sum;
}

상기 예 에서 1 에서 n 까지 매번 의 합 은 지난번 의 합 에 n 을 더 한 것 이기 때문에 우 리 는 교체 법 (전전 법) 이란 변수의 낡은 값 으로 새로운 값 을 계속 전달 하 는 과정 이라는 것 을 이해 하기 어렵 지 않다.
반복 3 단계:

교체 변 수 를 확정 합 니 다. sum

과 같은 직접적 이거 나 간접 적 으로 낡은 값 으로 새로운 값 을 계속 추정 하 는 변 수 를 확인 합 니 다.

교체 관계 식 구축: 변수의 낡은 값 에서 새로운 값 으로 추정 되 는 공식, 예 를 들 어 f (n) = f (n - 1) + n

교체 과정 을 통제 합 니 다. 교 체 는 무한 순환 이 불가능 합 니 다. 언제 교체 에서 물 러 날 지 제어 해 야 합 니 다!i > n 출시 순환

(2) 재 귀 는 무엇 입 니까?
마찬가지 입 니 다. 아래 의 이 예 를 보 여 주세요.

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

마찬가지 로 0 ~ n 의 합 을 구 하 는 것 이다. 이 코드 는 매번 함수 체 에서 자신의 함 수 를 호출 하 는 것 이다. 1 ~ n 의 합 은 두 부분 으로 나 눌 수 있 고 1 ~ n - 1 의 합 과 n 을 더 할 수 있다. 따라서 재 귀 하 는 사상 은 함수 나 서브 과정의 내부 에서 자신의 알고리즘 을 직접 또는 간접 적 으로 호출 하여 문 제 를 규모 가 축 소 된 같은 문제 의 서브 문제 로 전환 시 키 는 것 이다.
귀속 알고리즘 의 절차: 1. 귀속 공식 을 확정한다. 예 를 들 어 sum (n) = sum (n - 1) + n 2. 귀속 종료 조건 을 확정한다. 예 를 들 어 n = 1 종료 귀속
(3) 재 귀 와 교체, 누 구 를 선택 하 시 겠 습 니까?
간단 한 예 를 들 어 피 보 나 계 수열 을 풀 어 달라 고 부탁 하 다.

//1、    
int fib(int n )
{
    if(n<2) return 1;
    int f0 = 1,f1=1;
    for(int i = 2 ; i < n ; i++){
        int f2= f0+f1;
        f0=f1;f1=f2;
    }
    return f1;
}
//2、    
int fib1(int n)
{
    if (n <= 1) return 1;      
    return fib1(n-1) + fib1(n-2);  
}

예 를 들 어 교체 알고리즘 은 재 귀 알고리즘 이 간결 하지 않 지만 교체 알고리즘 은 효율 이 높 고 운행 시간 은 순환 횟수 에 비례 하 며 호출 함수 로 인 한 추가 비용 이 없다.
재 귀 버 전의 코드 는 매우 간단 하고 가 독성 이 강하 다.그러나 재 귀적 으로 치 명 적 인 단점 은 재 귀적 깊이 가 너무 깊 으 면 스 택 이 넘 칠 수 있다 는 것 이다!
우 리 는 자신의 함 수 를 호출 할 때마다 이 함수 가 종료 되 지 않 고 계속 실행 되 는 것 을 알 게 되 었 다.함수 호출 과정 에서 시스템 은 하나의 스 택 을 분배 합 니 다. 재 귀 깊이 가 깊 을 수록 스 택 의 점용 이 클 수록 그 결 과 는 스 택 이 넘 치 는 것 입 니 다.
그 러 니 교체 할 수 있 는 곳 에 서 는 재 귀 를 사용 하지 마라.여기 또 문제 가 있 네?재 귀 하 는 사상 이 간단 하고 생각 하기 쉽다. 그러면 어떻게 해야만 재 귀 하 는 사상 을 빌려 교체 하 는 알고리즘 을 쓸 수 있 습 니까?다음 절 은 통용 되 는 전환 방식 을 소개 한다.
(4) 재 귀 를 교체 하 는 통용 방식 으로 전환한다.
끝 재 귀 를 교체 로 바꾸다.
끝 재 귀: 재 귀 의 특수 한 상황, 함수 호출 이 함수 끝 에 나타 나 는 재 귀 방식.상술 한 두 가지 예 는 모두 꼬리 재 귀 를 입력 한다.
꼬리 재 귀 는 쉽게 교체 방식 으로 바 꿀 수 있다.여 기 는 구체 적 으로 설명 하지 않 겠 습 니 다.
비 꼬리 재 귀 를 교체 로 바꾸다.
비 꼬리 재 귀 를 교체 로 바 꾸 려 면 반드시 스 택 을 사용 해 야 합 니 다. 쉽게 말 하면 아 날로 그 함수 호출 스 택 입 니 다.
아니면 하나의 예 를 들 어 전환 방법 을 설명 합 니까?

//         
// ：   partition    
void QuickSort1(int beg, int end) 
{      
    if (end - beg <= 1) return;      
    int pos = partition(beg, end);      
    QuickSort1(beg, pos);      
    QuickSort1(pos + 1, end);  
} 
//           
void QuickSort2(int beg, int end) 
{      
    stack<pair<int ,int>> temp_stack;//       begin end  
    temp_stack.push(pair<int,int>(begin,end));
    while(!temp.empty())//          
    {
        pair<int,int>  tmp = temp_stack.top();
        temp_stack.pop();//      ，      ，      
        if(temp.second - tmp.first > 1)//       ，            ，      
        {
            int pos = partition(beg, end);  
            temp_stack.push(pair<int,int>(tmp.first,pos));
            temp_stack.push(pair<int,int>(pos+1,tmp.second));
        }
    }
} 

여기 서 스 택 을 이용 하여 매번 재 귀 하 는 첫 번 째 요 소 를 저장 하고 함수 호출 에 따 른 추가 비용 을 줄 이 며 시스템 스 택 의 넘 침 을 피 할 수 있 습 니 다.
물론 상기 예 는 간단 한 예 일 뿐 스 택 을 이용 하여 재 귀 알고리즘 을 교체 알고리즘 으로 바 꾸 는 사상 을 논술 했다.
재 귀적 인 중간 변수 가 증가 할 때 더 큰 데이터 구 조 를 이용 하여 함수 호출 의 중간 변 수 를 저장 해 야 하지만 사상 은 변 하지 않 는 다.
이 블 로 그 를 정리 한 이 유 는 이 블 로그 에서 재 귀 를 사용 하면 스 택 이 넘 치고 교체 버 전 으로 전환 하면 AC 를 쉽게 할 수 있 기 때문이다.