자바 재 귀적 운영 체제:재 귀적 미시적 해석 그림 분석

본 고 는 자바 재 귀 운행 의 메커니즘 인 재 귀 의 미시적 해 를 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
앞에서 말 했 듯 이 4.567915.와 4.567915.에서 우 리 는 각각 배열 과 링크 를 통 해 재 귀 를 응용 했다.그때 우 리 는 재 귀 에 대해 거시적인 이 해 를 했 을 뿐이다.재 귀 는 문 제 를 더욱 작은 문제 로 바 꾸 는 서브 과정 이다.이 절 에서 우 리 는 4.1 절 에서 배열 에 귀 속 된 응용 과 4.2 절 에서 링크 에 귀 속 된 응용 에 대해 미시적 인 해석 을 한다.
4.1 절 에서 배열 에 재 귀 되 는 응용
1)우 리 는 먼저 4.1 절의 코드 실현 을 살 펴 보 자.다음 과 같은 그림 이다.

더욱 잘 분석 하기 위해 서 우 리 는 상술 한 코드 의 마지막 문장 을 분할 하고 분할 결 과 는 다음 과 같다.
 
이때 n=arr.length=2:

2)현재 우 리 는 분 리 된 코드 를 분석 하여 이 를 위해 설명 한다.재 귀 함수 의 호출 은 본질 적 으로 함수 호출 이다.
 간단 한 분석 을 위해 서 우 리 는 두 개의 요소 만 있 는 배열 arr=[6,10]을 사용한다.
첫 번 째 호출:sum(arr,0)
sun(arr,0)을 사용 하여 호출 하고 방법 체 에 들 어간 후에 재 귀적 인 기본 조건 을 만족 시 키 지 못 하기 때문에 sum(arr,1)방법 을 계속 호출 합 니 다.다음 과 같 습 니 다.

두 번 째 호출:sum(arr,1)
 sun(arr,1)을 사용 하여 호출 하고 방법 체 에 들 어간 후에 재 귀적 인 기본 조건 을 만족 시 키 지 못 하기 때문에 sum(arr,2)방법 을 계속 호출 합 니 다.이때 호출 과정 은 다음 과 같 습 니 다.

 sum(arr,2)을 호출 할 때 재 귀적 기본 조건 을 만족 시 켰 기 때문에 결 과 는 0 으로 돌아 가 지난번 에 중 단 된 위치 로 돌아 갑 니 다.즉,다음 그림 에서 sum(arr,1)방법 중의 sum(arr,l+1)을 호출 합 니 다.다음 그림:
 

코드 는 인 터 럽 트 에서 계속 아래로 실행 되 고 arr[1]=10,x=0 을 되 돌려 줍 니 다.따라서 res=10 입 니 다.이때 반환 값 은 res=10 입 니 다.

 
이 때 코드 도 sum(arr,1)아버지의 호출,즉 sum(arr,0)으로 돌아 갑 니 다.

코드 는 인 터 럽 트 에서 계속 아래로 실행 되 고 arr[0]=6,x=10 을 되 돌려 줍 니 다.따라서 res=16 입 니 다.이때 반환 값 은 res=16 입 니 다.

재 귀 를 통 해 우리 의 최종 결 과 는 16 이다.
상기 과정 에서 재 귀 함수 의 호출 은 본질 적 으로 함수 호출(자체 함수)-즉,서로 다른 매개 변 수 를 사용 하여 같은 논 리 를 집행 하 는 것 임 을 입증 했다.
2.4.2 절 에서 링크 에 재 귀 된 응용(링크 에서 지정 한 모든 요소 값 삭제)
 1)우 리 는 먼저 4.2 절 중의 코드 실현 을 살 펴 보 자.다음 과 같은 그림 이다.

분석의 편 의 를 위해 우리 상대방 의 법 체 중의 코드 는 간단 한 표 지 를 한다.1,2,3.결 과 는 다음 과 같다.

 2)간단 한 분석 을 위해 아 날로 그 호출 을 진행 하고 6--->7--->8-->null 에서 요소 가 7 인 노드 를 삭제 합 니 다.
주의:아래 분석 에서 우 리 는 1,2,3 이라는 번 호 를 사용 하여 코드 가 실 행 된 위 치 를 표시 합 니 다.
첫 번 째 호출:
먼저 헤드 노드 가 6 인 체인 테이블 에 들 어 갑 니 다.귀속 의 기본 적 인 종료 조건 을 만족 시 키 지 못 하기 때문에 두 번 째 호출 을 다시 촉발 합 니 다.이때 체인 테이블 은 헤드 노드 가 7 인 체인 테이블 로 변 합 니 다.

두 번 째 호출:
이때 체인 테이블 의 두 결점 은 7 로 변 했다.귀속 의 기본 적 인 종료 조건 을 만족 시 키 지 못 하기 때문에 다시 세 번 째 호출 을 촉발 했다.이때 체인 테이블 은 두 결점 이 8 인 체인 테이블 로 변 했다.

세 번 째 호출:
 이때 체인 테이블 의 머리 결점 은 8 로 바 뀌 었 다.귀속 의 기본 적 인 종료 조건 을 만족 시 키 지 못 하기 때문에 네 번 째 호출 을 다시 촉발 했다.이때 체인 테이블 은 빈 체인 테이블 로 바 뀌 었 다.

네 번 째 호출 에서 이 때 는 재 귀적 기본 조건 을 만족 시 켰 기 때문에 지난번 에 중 단 된 위치,즉 2 의 위치 로 돌아 가 반환 값 은 null 입 니 다.다음 과 같 습 니 다.
 
이때 의 링크 는 두 점 이 8 인 링크 입 니 다.위 그림 의 노란색 구역 과 같이 세 번 째 코드 를 실행 한 후에 돌아 온 결 과 는 두 점 이 8 인 링크 입 니 다.즉,8->null 이 고 이 결 과 를 이전 단계 로 호출 합 니 다.즉,레이 블 이 2 인 곳 으로 되 돌려 결 과 를 얻 었 습 니 다.7->8->null 의 링크 입 니 다.

그 다음 에 세 번 째 단 계 를 계속 실행 합 니 다.이때 링크 7->8->null 은 삭제 조건 을 만족 시 킵 니 다.즉,head.val=val=7 은 head.next 를 실행 하고 최종 결 과 는 8->null 로 돌아 갑 니 다.다음 과 같 습 니 다.
 
부모 호출 의 인 터 럽 트 위치 로 돌아 가 얻 은 결 과 는 6->8->null 입 니 다.그리고 세 번 째 코드 를 실행 하여 이때 링크 의 head.val 이 val=7 과 같은 지 판단 합 니 다.이때 링크 가 만족 하지 않 으 면 head,즉 6-8->null 로 돌아 갑 니 다.

 이 재 귀적 호출 이 끝 났 습 니 다.완성 과정 은 다음 과 같 습 니 다.

재 귀적 호출 은 대가 에 의 한 것 입 니 다.함수 호출(시간 지출)+시스템 스 택 공간 이지 만 재 귀적 쓰기 논 리 를 사용 하 는 것 이 더욱 간단 합 니 다.
자바 알고리즘 과 관련 된 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 고 에서 말 한 것 이 여러분 의 자바 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.