1.서론 의 귀착

1253 단어 자바귀착 하 다
이 장 에서 비교적 흥미 로 운 부분 을 따 내 면 먼저 재 귀 에 관 한 약술 이다.
  귀속 에는 두 가지 기본 법칙 이 있다.
1.
기준 상황:귀속 하지 않 아 도 해답 을 구 할 수 있다
2.
계속 추진:재 귀적 으로 해결 해 야 하 는 상황 에 대해 재 귀적 호출 은 반드시 기준 상황 으로 추진 해 야 한다.
  다음은 몇 가지 예 를 들 겠 습 니 다.
예 1 끝 없 는 귀환

public static int bad(int n){
     if(n==0)
        return 0;
     else
        return bad(n/3+1)+n-1;
}

  이 예 에서 bad(1)는 bad(1)를 반복 적 으로 구 합 니 다.마찬가지 로 bad(2)도 마찬가지 입 니 다.죽음 의 순환 에 빠 질 것 이다.
예 2 출력 정수
  정수 n 이 설치 되 어 있 으 며 인쇄 를 원 합 니 다.유일한 IO 는 하나의 숫자 만 처리 하고 출력 할 수 있 습 니 다(printDigit).분석:76321 을 인쇄 하려 면 먼저 7632 를 인쇄 하고 1 을 친다.인쇄 1 은 printDigit(n%10)만 하면 됩 니 다.7632 를 인쇄 하면 print(76321/10)를 사용 할 수 있 습 니 다.

public static void print(long n){
	if(n>=10)
		print(n/10);
	printDigit(n%10);
}

  그러나 이 예 는 그다지 효율 적 이지 않다.왜냐하면 mod 는 매우 시간 이 걸 리 기 때문이다.n%10=n-(n/10)*10.
  그래서 귀환 의 세 번 째 법칙 을 끌 어 낸다.
3.
설계 법칙:모든 재 귀 호출 이 실 행 될 수 있다 고 가정 합 니 다.
  재 귀 프로그램 을 작성 할 때 네 번 째 기본 법칙 을 기억 해 야 합 니 다.
4.
합성 효과 법칙:한 문제 의 동일 한 실례 를 구 할 때 서로 다른 귀속 호출 에서 중복 작업 을 하지 마 세 요.
  따라서 피 보 나치 와 같은 간단 한 수학 함수 값 을 재 귀적 으로 계산 하 는 것 은 적절 하지 않다.

좋은 웹페이지 즐겨찾기