자바 의 교체 와 재 귀적 상세 설명

머리말
최근 에 책 을 읽다 가 이 내용 을 보 니 꽤 수확 이 있 는 것 같다.반복 적 으로 사용 하 는 것 은 순환(for,while,do...wile)이나 교체 기 입 니 다.순환 조건 이 만족 하지 않 을 때 종료 합 니 다.한편,재 귀 는 보통 함수 재 귀 이 고 자신 이 자신 을 호출 할 수도 있 으 며 직접 호출 할 수도 있다.즉,방법 A 호출 방법 B 이 고 방법 B 는 반대로 호출 방법 A 를 호출 하 며 재 귀 탈퇴 조건 은 if,else 문 구 는 조건 이 기본 에 부합 할 때 종료 한다.
위 는 교체 와 재 귀적 인 문법 적 특성 인 데 그들 은 자바 에서 어떤 차이 가 있 습 니까?다음은 이 글 을 통 해 자세히 알 아 보 겠 습 니 다.
돌아오다
교체 하면 수학 표현 식 을 제시 할 수 밖 에 없습니다.n!=n*(n-1)*(n-2)*...*1곱셈 을 계산 하 는 방법 은 매우 많다.일정한 수학 기초 가 있 는 사람 은 모두 알 고 있 기 때문에 코드 의 실현 은 바로 다음 과 같이 쓸 수 있다.
코드 1

int factorial (int n) {
 if (n == 1) {
  return 1;
 } else {
  return n*factorial(n-1);
 }
} 

상기 코드 를 실행 할 때 사실은 기 계 는 일련의 곱셈 을 집행 해 야 한다.n!=n*(n-1)!→factorial(n) →factorial(n-1) →...→factorial(n-2) .따라서 끊임없이 추적(지난번 에 계 산 된 결 과 를 추적)하고 곱셈 으로 계산(곱셈 체인 구축)해 야 한다.이런 끊임없이 자신의 연산 형식 을 호출 하 는 것 을 재 귀 라 고 한다.재 귀 는 선형 재 귀 와 수 형 재 귀 로 나 눌 수 있다.정 보 량 은 알고리즘 의 입력 에 따라 선형 으로 증가 하 는 재 귀 를 선형 재 귀 라 고 한다.계산 n!(곱셈)은 선형 귀속 이다.N 이 커지 면서 계산 에 걸 리 는 시간 이 선형 으로 늘 어 나 기 때문이다.또 다른 정 보 량 은 입력 이 증가 함 에 따라 지수 가 증가 하 는 것 을 트 리 재 귀 라 고 한다.
교체
다른 계산 n!먼저 1 곱 하기 2 를 계산 한 다음 그 결과 로 3 을 곱 한 다음 에 사용 한 결 과 를 4 로 곱 하고 N 까지 곱 하 는 방식 이다.프로그램 이 실 현 될 때 계수 기 를 정의 할 수 있 습 니 다.곱셈 을 할 때마다 계수 기 는 N 이 될 때 까지 한 번 씩 증가 합 니 다.코드 는 다음 과 같 습 니 다:
부호 2

int factorial (int n) {
 int product = 1;
 for(int i=2; i<n; i++) {
  product *= i;
 }
 return product;
}

코드 1 에 비해 코드 2 는 곱셈 체인 을 구축 하지 않 았 다.모든 계산 을 할 때 현재 결과(product)와 i 의 값 만 알 면 됩 니 다.이런 계산 형식 을 교체 라 고 부른다.교체 에는 이러한 몇 가지 조건 이 있다.1.초기 값 이 있 는 변수 가 있다.2.변수 값 이 어떻게 업데이트 되 는 지 설명 하 는 규칙 입 니 다.3.하나의 종료 조건.순환 3 요소:순환 변수,순환 체 와 순환 종료 조건).재 귀 와 같다.시간 은 입력 의 증가 에 따라 선형 을 나타 내 는 것 을 선형 교체 라 고 할 수 있다.
3.교체 VS 재 귀
두 프로그램 을 비교 해 보면 우 리 는 그들 이 거의 똑 같 아 보이 고 특히 수학 함수 에 있어 서 는.n 계산 중!때,그들의 계산 걸음 수 는 모두 n 의 값 과 정비례 한다.그러나 우리 가 프로그램의 측면 에서 그들 이 어떻게 운행 하 는 지 를 고려한다 면 이 두 알고리즘 은 크게 다르다.
(주:원문에서 그 차이 점 에 대해 약간 언급 했 는데 여 기 는 번역 하지 않 겠 습 니 다.다음은 필자 가 스스로 내용 을 정리 하 는 것 입 니 다.)
먼저 재 귀 를 분석 하고 재 귀 의 가장 큰 점 은 복잡 한 알고리즘 을 똑 같은 반복 가능 한 절차 로 분해 하 는 것 이다.따라서 재 귀 를 사용 하여 하나의 계산 논 리 를 실현 하 는 데 짧 은 코드 만 있 으 면 해결 할 수 있 고 이런 코드 도 쉽게 이해 할 수 있다.그러나 재 귀 는 대량의 함수 호출 을 의미한다.함수 호출 의 부분 상 태 를 스 택 으로 기록 한 이유.그래서 이렇게 하면 대량의 공간 을 낭비 할 수 있 고 너무 깊 게 돌아 가면 창고 가 넘 칠 수도 있다.
다음은 교체 분석.사실 재 귀 는 모두 교체 로 대체 할 수 있다.그러나 재 귀 는 간단 하고 알 기 쉬 워 서 교체 가 어색 하 다.특히 복잡 한 장면 을 만 났 을 때하지만 코드 의 이해 하기 어 려 운 점도 뚜렷 하 다.교체 의 효율 은 재 귀 보다 높 고 공간 소모 도 적다.
      재 귀 에는 반드시 교체 가 있 지만 교체 에 반드시 재 귀 가 있 는 것 은 아니 며 대부분 서로 전환 할 수 있다.
      교체 할 수 있 는 것 은 재 귀 를 사용 하지 마 세 요.재 귀 호출 함 수 는 공간 을 낭비 할 뿐만 아니 라 재 귀 가 너무 깊 으 면 스 택 의 넘 침 을 초래 하기 쉽 습 니 다.
사각형 재 귀
앞서 소 개 했 듯 이 트 리 는 입력 에 따라 증가 하 는 정 보 량 이 지수 급 으로 증가 했다.비교적 전형 적 인 것 은 바로 피 보 나치 수열 이다.

문자 로 묘사 하면 피 보 나치 수열 에서 앞의 두 숫자의 합 은 세 번 째 숫자 와 같다.0,1,1,2,3,5,8,13,21...
귀속 실현 코드 는 다음 과 같다.

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

계산 과정 에서 계산factorial(1) 을 위해 서 는 프로그램 이 먼저 계산fib(5)과fib(4) ,계산fib(3) 을 하려 면 프로그램 역시 먼저 계산fib(4)과fib(3) 이 필요 하 다.이 과정 에서 fib(3)를 두 번 계산 했다.
위 에서 분석 한 계산 과정 에서 결론 을 얻 을 수 있다.재 귀 를 이용 하여 피 보 나치 수열 에 불필요 한 계산 이 존재 한 다 는 것 이다.
위 에서 언급 한 바 와 같이 재 귀 할 수 있 는 알고리즘 은 일반적으로 교체 로 이 루어 질 수 있 고 피 보 나치 수열 의 계산 도 마찬가지다.

int fib (int n) {
 int fib = 0;
 int a = 1;
 for(int i=0; i<n; i++) {
  int temp = fib;
  fib = fib + a;
  a = temp;
 }
 return fib;
}

재 귀 방식 을 사용 하면 불필요 한 계산 이 있 지만 교체 로 대체 할 수 있다.그러나 재 귀 가 완전히 대 체 될 수 있다 는 뜻 은 아니다.재 귀적 으로 더 읽 을 수 있 기 때문이다.
총결산
이상 은 이 글 의 전체 내용 입 니 다.본 논문 의 내용 이 여러분 이 자바 를 배우 거나 사용 하 는 데 도움 이 되 기 를 바 랍 니 다.궁금 한 점 이 있 으 면 댓 글 을 남 겨 주 십시오.