데이터 구조 와 알고리즘 의 아름다움 학습 노트 (10 장) 재 귀적

제10 장 귀속
재 귀 는 매우 중요 하 다. 이 편 은 모두 재 귀 된 지식 과 연습 이다.
좋 은 예 가 이 해 를 돕는다.
주말 에 너 는 여자 친 구 를 데 리 고 영화관 에 가서 영 화 를 보 는데, 여자 친구 가 너 에 게 물 었 다. 우 리 는 지금 몇 번 째 줄 에 앉 아 있 니?영화관 안 이 너무 어 두 워 서 잘 보이 지 않 아서 셀 수가 없어 요. 이제 어 떡 해요?
당신 이 프로그래머 라 는 것 을 잊 지 마 세 요. 이것 은 정말 어렵 지 않 습 니 다. 재 귀적 으로 도움 이 되 기 시 작 했 습 니 다.그래서 당신 은 앞 줄 에 있 는 사람 에 게 그 가 몇 번 째 줄 이 냐 고 물 었 습 니 다. 당신 은 그의 숫자 에 하 나 를 더 하면 자신 이 어느 줄 에 있 는 지 알 수 있 을 것 이 라 고 생각 합 니 다.그런데 앞 사람 도 잘 안 보 여요. 그래서 앞 사람 한테 도 물 어 봤 어 요.이렇게 일렬 로 물 어보 고 첫 번 째 줄 에 있 는 사람 에 게 내 가 첫 번 째 줄 에 있다 고 말 한 다음 에 이렇게 일렬 로 숫자 를 돌려 준다.네 앞 사람 이 너 에 게 그 가 어느 줄 에 있 는 지 알려 줄 때 까지 너 는 답 을 알 게 될 것 이다.
이것 은 바로 매우 표준적 인 귀속 구 해 문제 의 분해 과정 이다. 가 는 과정 을 '귀속' 이 라 고 하고 돌아 오 는 과정 을 '귀속' 이 라 고 한다.기본적으로 모든 귀속 문 제 는 추이 공식 으로 표시 할 수 있다.방금 이 생활 속 의 예 를 우 리 는 전달 공식 으로 그것 을 나타 내 는 것 이 바로 이렇다.

f(n)=f(n-1)+1   ，f(1)=1

f (n) 는 자신 이 어느 줄 에 있 는 지 알 고 싶다 는 뜻 이 고, f (n - 1) 는 앞 줄 에 있 는 줄 수 를 나타 내 며, f (1) = 1 은 첫 번 째 줄 에 있 는 사람 이 자신 이 첫 번 째 줄 에 있 는 것 을 알 고 있다 는 뜻 이다.이 푸 시 공식 이 있 으 면 우 리 는 쉽게 그것 을 재 귀 코드 로 바 꿀 수 있다. 다음 과 같다.

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

예 2
만약 여기에 n 개의 계단 이 있다 면, 매번 당신 은 1 개의 계단 이나 2 개의 계단 을 넘 을 수 있 습 니 다. 이 n 개의 계단 을 걸 으 면 몇 가지 방법 이 있 습 니까?만약 7 개의 계단 이 있다 면, 너 는 2, 2, 2, 1 이렇게 올 라 갈 수도 있 고, 1, 2, 1, 1, 2 이렇게 올 라 갈 수도 있다. 어쨌든 걷 는 방법 이 매우 많다. 그러면 어떻게 프로 그래 밍 으로 총 몇 가지 걷 는 방법 을 구 할 수 있 니?
우 리 는 곰 곰 이 생각해 보 았 다. 실제로 첫 번 째 걸음 의 걷 는 방법 에 따라 모든 걷 는 방법 을 두 가지 로 나 눌 수 있다. 첫 번 째 유형 은 첫 번 째 걸음 으로 한 계단 을 걷 는 것 이 고 다른 유형 은 첫 번 째 걸음 으로 두 계단 을 걷 는 것 이다.그래서 n 계단 의 걷 는 방법 은 먼저 1 단계 후 n - 1 계단 의 걷 는 방법 에 먼저 2 단계 후 n - 2 계단 의 걷 는 방법 을 더 하 는 것 과 같다.공식 적 으로 말 하면:

f(n) = f(n-1)+f(n-2)

전달 공식 이 있 으 면 재 귀 코드 는 기본적으로 절반 이 완성 된다.종료 조건 을 다시 한번 살 펴 보 겠 습 니 다.계단 이 하나 있 을 때, 우 리 는 더 이상 재 귀 할 필요 가 없고, 단지 하나의 방법 만 있 을 뿐이다.그래서 f (1) = 1.이 귀속 중지 조건 은 충분 합 니까?우 리 는 n = 2, n = 3 이렇게 비교적 작은 수로 시험 해 볼 수 있다.
n = 2 시, f (2) = f (1) + f (0).재 귀 종료 조건 이 f (1) = 1 만 있 으 면 f (2) 는 풀 수 없다.그래서 f (1) = 1 이라는 귀속 중지 조건 을 제외 하고 f (0) = 1 은 0 개의 계단 을 걷 는 방법 이 있다 는 것 을 나타 낸다. 그러나 이렇게 하면 정상 적 인 논리 적 사고 에 부합 되 지 않 는 다.그래서 우 리 는 f (2) = 2 를 일종 의 중지 조건 으로 삼 아 2 개의 계단 을 걷 는 것 을 표시 할 수 있다. 두 가지 방법 이 있 는데 한 걸음 에 다 걷 거나 두 걸음 으로 나 누 어 걸 을 수 있다.
따라서 재 귀 종료 조건 은 f (1) = 1, f (2) = 2 다.이 럴 때 n = 3, n = 4 를 가지 고 이 종료 조건 이 충분 하고 정확 한 지 검증 할 수 있 습 니 다.
우 리 는 귀환 중지 조건 과 방금 얻 은 추이 공식 을 함께 놓 으 면 이렇다.

f(1) = 1;
f(2) = 2;
f(n) = f(n-1)+f(n-2)

최종 코드

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

귀속 수요 만족 의 세 가지 조건
1. 한 문제 의 해 는 몇 개의 문제 의 해 로 나 눌 수 있다.
무슨 문제 입 니까?하위 문 제 는 데이터 규모 가 더 작은 문제 다.예 를 들 어 앞에서 말 한 영화관 의 예 를 들 어 '자신 이 어느 줄 에 있 느 냐' 는 문 제 는 '앞 줄 에 있 는 사람 이 어느 줄 에 있 느 냐' 는 문제 로 나 눌 수 있다.
2. 이 문 제 는 분 해 된 서브 문제 와 데이터 규모 가 다른 것 을 제외 하고 해결 방향 이 똑 같 습 니 다.
예 를 들 어 영화관 의 그 예 를 들 어 당신 은 '자신 이 어느 줄 에 있 습 니까?' 라 는 생각 을 풀 었 고 앞 줄 의 사람들 이 '자신 이 어느 줄 에 있 습 니까?' 라 는 생각 을 풀 었 던 것 과 똑 같 습 니 다.
3. 귀속 종료 조건 이 존재
문 제 를 하위 문제 로 분해 하고 하위 문 제 를 하위 문제 로 분해 하 며 한 층 한 층 분해 해 나 가면 무한 순환 이 존재 하지 않 으 므 로 중지 조건 이 필요 하 다.
아니면 영화관 의 예 입 니까? 첫 번 째 줄 의 사람들 은 더 이상 누구 에 게 도 물 어보 지 않 아 도 자신 이 어느 줄 에 있 는 지 알 수 있 습 니 다. 즉, f (1) = 1 입 니 다. 이것 이 바로 재 귀적 인 종료 조건 입 니 다.
재 귀 코드 를 쓰 는 관건 은 큰 문 제 를 작은 문제 로 분해 하 는 규칙 을 찾 고 이 를 바탕 으로 전달 공식 을 쓴 다음 에 종료 조건 을 퇴고 한 다음 에 전달 공식 과 종료 조건 을 코드 로 번역 하 는 것 이다.
재 귀 코드 를 작성 하 는 관건 은 재 귀 를 만 나 기만 하면 우 리 는 그것 을 전달 공식 으로 추상 화 하 는 것 이다. 한 층 의 호출 관 계 를 생각 하지 않 고 인간 의 뇌 로 재 귀 하 는 모든 절 차 를 분해 하려 고 하지 않 는 다 는 것 이다.
하지만 재 귀적 코드 도 쓰기 어렵 고 이해 하기 어렵다.재 귀 코드 를 만 드 는 관건 은 자신 을 돌아 가지 않 는 것 이다. 정확 한 자 세 는 전달 공식 을 쓰 고 종료 조건 을 찾 아 재 귀 코드 로 번역 하 는 것 이다.
재 귀 코드 는 간결 하고 효율 적 이지 만 재 귀 코드 도 단점 이 많다.예 를 들 어 스 택 넘 침, 중복 계산, 함수 호출 시간 이 많 고 공간 복잡 도가 높 기 때문에 재 귀 코드 를 작성 할 때 이런 부작용 을 잘 제어 해 야 합 니 다.
 
재 귀적 연습
1. 현재 숫자 1, 12, 123, 1234, 12345.................................................................
재 귀 공식 법칙

f(n)=f(n-1)*10+n

종료 조건

f(1)=1

코드

public class Test01 {
    public static int f(int n){
        if(n==1){
            return 1;
        }
        return f(n-1)*10+n;
    }

    public static void main(String[] args) {
        System.out.println(f(9));
    }
}