[데이터 구조] 재 귀 와 스 택

귀착 하 다
재 귀 란 한 함수 나 데이터 구조의 정의 에서 직접 (또는 간접) 정의 자체 가 나타 나 는 것 을 말한다. 이것 은 끊임없이 깊이 있 고 세분 화 되 는 과정 이다.
재 귀적 인 사상 은 비교적 교묘 하기 때문에 자신 이 많이 생각 하거나 다른 사람의 코드 를 많이 이해 해 야 한다.
 
1) 함수 정의
예 를 들 면:
곱 하기 함수 n! =n * (n-1) * ... * 1

int Fact(int n)
{
    if(n == 0) return 1;    /* n  0，    1*/

    else return n * Fact(n-1);    /*   n-1  Fact  ，  n  */
}

피 폴 라 치 수열, 세 번 째 수 는 앞의 두 수의 합 과 같다.

int Fibonacci(int n)
{
    if(n == 1||n ==2) return 1;    /*     1*/

    else return Fib(n-1) + Fib(n-2);    /*n n               */
}

 
2) 데이터 구조 정의
예 를 들 면:
링크 노드

typedef struct LNode
{
    Elemtype data;

    struct LNode *next;    /*                 */

} LNode, *LinkList;

링크 노드 의 구 조 를 이용 하여 표 의 모든 노드 를 옮 겨 다 닌 다.

/*-------      --------*/

void Traverse1(LinkList L)
{
    while(L != NULL)        /*   ，   */
    {
        cout<data;

        L = L->next;
    }
}



/*-------         -------*/

void Traverse2(LinkList L)
{
    if(L == NULL) cout<data;

    Traverse2(L->next);
    }
}

위의 코드 를 관찰 한 결과 재 귀 는 순환 을 실현 할 수 있 는 기능 을 발견 할 수 있다.
 
3) 문제 의 귀속 해법
문 제 를 처리 할 때 필요 한 조건 은 문제 의 본질 과 같은 문 제 를 해결 하 는 것 이 므 로 재 귀 알고리즘 을 사용 할 수 있다.
예 를 들 면:
질문
A, B, C 로 각각 세 개의 기둥 이 있 는데, A 기둥 위 에 작은 것 에서 큰 것 으로 배 열 된 n 개의 원반 이 위 에서 아래로 놓 여 있 는데, 문 제 는 어떻게 A 기둥 의 원반 을 모두 C 기둥 으로 옮 기 고 원반 의 원래 순 서 를 유지 하 느 냐 하 는 것 이다.매번 원반 하나만 움 직 일 수 있 고, 큰 원반 은 작은 원반 아래 에 있어 야 한다.
[큰 사고]
1. C 를 보조 기둥 으로 하고 A 의 앞 n - 1 개의 원반 을 B 로 이동 한 다음 n 번 째 원반 을 C 로 이동한다.
2. A 를 보조 기둥 으로 하여 B 의 n - 1 원반 을 C 로 이동한다.
3. 두 번 째 단 계 는 첫 번 째 단계 와 같은 조작 을 포함 하고 A 와 B 의 '신분' 만 바 뀌 기 때문에 재 귀 함수 에는 앞의 두 단계 의 내용 이 포함 되 어 있다.

#include 
using namespace std;

void move(char main1, int n, char main2)
{
	static int timer = 1;

	cout<>n;
	Hanoi(n,t1,t2,t3);
}

 
재 귀 작업 창고
고급 언어 로 제 작 된 프로그램 에서 호출 함수 와 호출 된 함수 간 의 링크 및 정보 교환 은 스 택 의 지원 이 필요 합 니 다.
여러 함수 가 내장 호출 을 구성 할 때 '먼저 호출 한 후 되 돌아 오기' 의 원칙 에 따라 상기 함수 간 의 정보 전달 과 제어 전 이 는 반드시 스 택 을 통 해 이 루어 져 야 합 니 다. 즉, 시스템 은 전체 프로그램 이 실 행 될 때 필요 한 데이터 공간 을 하나의 스 택 에 배치 해 야 합 니 다.
현재 실행 중인 함수 의 데이터 영역 은 스 택 꼭대기 에 있어 야 합 니 다.
 
재 귀 함수 의 운행 과정 은 여러 함수 의 내장 호출 과 유사 하 며, 호출 함수 와 호출 된 함수 만 같은 함수 입 니 다.따라서 매번 호출 과 관련 된 중요 한 개념 은 재 귀 함수 가 실 행 될 때의 '차원' 이다.
재 귀 함수 의 정확 한 집행 을 확보 하기 위해 시스템 은 '재 귀 작업 스 택' 을 전체 재 귀 함수 운행 기간 에 사용 하 는 데이터 저장 소 로 설정 해 야 합 니 다.
각 층 의 재 귀 에 필요 한 정 보 는 하나의 업무 기록 을 구성 하 는데 그 중에서 모든 실제 인삼, 모든 부분 변수, 그리고 윗 층 의 반환 주 소 를 포함한다.
한 층 에 들 어 갈 때마다 새로운 작업 기록 이 창고 에 들 어 옵 니 다.
한 층 씩 재 귀 할 때마다 창고 꼭대기 에서 작업 기록 이 팝 업 됩 니 다.
현재 실행 층 의 작업 기록 을 '활동 기록' 이 라 고 합 니 다.
 
일반적인 재 귀 과정 에 대해 서 는 재 귀 알고리즘 을 실행 하 는 과정 에서 재 귀 작업 스 택 의 상태 변 화 를 모방 하여 해당 하 는 비 재 귀 알고리즘 을 직접 작성 할 수 있 습 니 다. 즉, 스 택 을 이용 하여 재 귀 과정 을 제거 할 수 있 습 니 다.