자바 간단 한 재 귀 작업 방법 인 스 턴 스 실현

머리말
데이터 구조 알고리즘 디자인 에서 또는 한 방법의 구체 적 인 실현 을 할 때'재 귀'라 는 방법 이 있 는데 이런 방법 은 사상 적 으로 그리 어렵 지 않 지만 실현 할 때 주의해 야 할 것 이 있다.많은 재 귀 알고리즘 은 해당 하 는 순환 으로 대체 할 수 있 지만 추상 적 이 고 복잡 한 알고리즘 에 대해 재 귀 하지 않 아 도 이해 하고 실현 하기 어렵다.
재 귀 는 직접 재 귀 와 간접 재 귀 로 나 뉘 어 두 개의 작은 직접 재 귀 를 간단하게 공유 합 니 다.
재 귀적 인 개념 에 대해 서 는 사실 자신 을 정의 하 는 것 으로 간단하게 이해 할 수 있다.어 렸 을 때 주인공 을'상 발'이 라 고 부 르 는 드라마'늑대 독 꽃'을 본 기억 이 있다.그러나 문맹 인 선생님 이 그 에 게 이름 을 물 었 더 니'상 발'이 라 고 말 했다.'어느"자주 보 내 요!""어느 머리?""자주 보 내 는 머리 야!"결국 2 교시 선생님 은 한 무리의 어린이 들 에 게"자주 보 내 는 것,자주 보 내 는 것,바보 의 바보,바보 의 참외"라 고 외 치 게 하 셨 다.본론 으로 돌아 가면 대부분의 상황 에서 재 귀 는 하나의 생각 이나 정 의 를 해석 하 는 합 리 적 인 방법 임 이 분명 하 다.사상 적 으로 수학 에서 배 웠 던 수학 귀납법 과 유사 하 다.
재 귀적 실현:
재 귀적 실현 은 두 가지 가 있 습 니 다.재 귀적 옵션 과 비 재 귀적 옵션,후 자 는 기본 상황(base case)이 됩 니 다.기본 적 인 상황 은 재 귀적 인 종결 상황 으로 기본 적 인 상황 이 없 거나 잘 처리 하지 못 하면 무한 한 재 귀 를 초래 할 수 있다.이것 은 우리 가 원 하지 않 는 결과 이다.순환 적 으로 실현 하 는 가장 관건 적 인 것 은 기초 상황 을 잘 처리 하 는 것 이다.구체 적 인 사례 를 결합 하여 거 슬러 올 라 가 는 과정 을 말 하 다.
다음은 두 개의 애플 릿 을 쓰 겠 습 니 다.
1.계단 오 르 기 알고리즘:한 계단 에 n 개의 계단 이 있 는 것 을 알 고 있 습 니 다.매번 에 하나 또는 두 개의 계단 을 올 라 갈 수 있 습 니 다.모두 몇 가지 다른 방법 이 있 는 지 구 합 니 다.
방법 은 다음 과 같다.

재 귀 함 수 는 반환 값 이 없 는 것 보다 귀 찮 은 점 이 있 습 니 다.한 함수 에 반환 값 이 하나 밖 에 없 기 때문에 재 귀 는 기본 적 인 상황 이 존재 해 야 하기 때문에 if 판단 으로 재 귀 를 중지 해 야 합 니 다.그래서 모든 if 나 else 뒤에 return 이 있 습 니 다.이렇게 하면 함수 가 모든 상황 에서 하나의 반환 값 만 있 음 을 보증 합 니 다.
이 알고리즘 을 분석 해 보 세 요.
A:만약 에 0 개의 계단 이 있다 면 0 가지 방법 이 있 습 니 다.이 건 더 말 할 필요 가 없습니다.
B:계단 이 하나 있 으 면 한 가지 방법 이 있어 요.
C:계단 이 두 개 있 으 면 두 가지 방법 이 있 습 니 다.한 번 에 두 개 씩);
이상 의 B 와 C 는 기본 적 인 상황 이다.
D:다음은 재 귀 입 니 다.계단 수가 2 개 보다 많 으 면 먼저 첫 번 째 단 계 는 두 가지 선택 이 있 습 니 다.첫 번 째 로 1 개 를 걷 거나 첫 번 째 로 두 개 를 걷 습 니 다.이렇게 하면 첫 번 째 뒤의 걷 는 방법 을 제외 하고 두 가지 상황 이 있다.climb Stairs(n-1)와 climb Stairs(n-2).이렇게 해서 기초 상황(즉 n=1 또는 n=2 의 상황)이 나타 날 때 까지 이곳(기초 상황)으로 돌아 간 다음 에 거 슬러 올 라 가기 시작 했다.이것 이 바로 재 귀 와 밀접 한 관 계 를 가 진'거 슬러 올 라 가기'이다.돌 이 켜 보면 말 그대로 결과 에서 거꾸로 돌아 가 전체 과정 을 찾 아 이 경 로 를 분석 하거나 실현 하 는 과정 이 라 고 할 수 있다.
주의해 야 할 것 은 이 알고리즘 은 사고방식 이 간단 하지만 복잡 도가 낮 아 지지 않 고 창고 보존 문제(사실 재 귀적 인 디자인 은 두 개의 귀속 방식(climb(n)에 climb(n-1)과 climb(n-2)을 포함 하 는 것 을 피해 야 한다.이런 조작 은 창고 개척 공간 을 n 의 증가 에 따라 지수 형 으로 증가 시 킬 수 있다.최종 절 차 는 쉽게 무 너 집 니 다).그리고 계단 의 수량 이 일정 수량 이 많 을 때 경 계 를 넘 기 때문에 재 귀 절 차 는 어느 정도 에 사상 실현 디자인 에 있어 간단하게 이해 하 는 것 입 니 다.
다음은 소스 코드:

package leetcode;

public class ClimbStairs {
//	**************************************************************
	public int climbStairs(int n) {
 int i=1;
		 if(n<=0)
			return 0;
		 if(n==1){
			 return i;
		 }
		 if(n==2){
			 i++;
			 return i;
		 }
		 else
			 return climbStairs(n-1)+climbStairs(n-2);
 }
//**************************************************************
 	 public static void main(String []args){
		 ClimbStairs cs=new ClimbStairs();
		 int a =cs.climbStairs(4);
	 	 System.out.println(a);
	 }

}

그 다음 에 몇 가지 전형 적 인 재 귀 문제 도 있다.예 를 들 어 미로 문제 나 가장 전형 적 인 한 노 타 문제,아래 에 모두 소스 코드 를 제시 하고 모두 함께 공부 해 보 자.
한 노 타 문제:한 번 에 한 접시 만 이동 할 수 있 습 니 다.큰 접 시 를 작은 접시 에 놓 으 면 안 된다.접시 가 두 기둥 사이 로 움 직 이 는 순간 을 제외 하고 접 시 는 모두 기둥 위 에 있어 야 한다.(이 세 가지 요구 에 따라 접 시 를 시작 기둥 A 에서 목표 기둥 C 로 모두 이동)

코드 는 다음 과 같 습 니 다:
기본 상황:n=1 시 에 재 귀 를 중지 하고 역 추적 을 한다.

public class HanNuoTower {
	public void tower(int n,char s,char m,char e)//n   s  m       e
	{
		if(n==1)
			move(s,e);
		else
		{
			tower(n-1,s,e,m);
			move(s,e);
			tower(n-1,m,s,e);
		}
	}
	public void move(char s,char e){
		System.out.println("move "+s+" to "+e);
	}
	public static void main(String []args){
		HanNuoTower hnt =new HanNuoTower();
		hnt.tower(4,'A','B','C');
	}

}

미로 걷 기:2 차원 배열 은 하나의 미 로 를 구성 합 니 다.1 은 통 로 를 표시 하고 0 은 통 하지 않 습 니 다.하나의 경 로 를 찾 아 시작 점(traverse 함수 의 매개 변수)에서 종점(오른쪽 아래 각 점)까지 찾 습 니 다.
기본 상황:row=grid.length-1&column=grid[0].length-1 시 done=true;

public class Maze {
	private final int TRIED=3;
	private final int PATH=7;
	
	private int [][] grid={	{1,1,1,0,0,1,0,1,0,0},
										{0,0,1,1,1,0,0,0,0,0},
										{1,0,1,0,0,0,1,1,1,1},
										{1,1,1,1,1,0,0,0,1,1},
										{0,0,0,0,1,1,1,0,0,0},
										{1,0,1,0,1,0,0,1,0,0},
										{1,0,0,1,1,1,1,1,1,1}		};
	public boolean traverse(int row,int column){
		boolean done =false;
		if(valid(row,column))
		{
			grid[row][column]=TRIED;
			if(row==grid.length-1&&column==grid[0].length-1)
				done=true;
			else
			{
				done=traverse(row+1,column);//down
				if(!done)
					done=traverse(row,column+1);//right
				if(!done)
					done=traverse(row-1,column);//up
				if(!done)
					done=traverse(row,column-1);//left
			}
			if(done)
				grid[row][column]=PATH;
		}
		return done;
	}
	private boolean valid(int row,int column){
		boolean result=false;
		if(row>=0&&row<grid.length&&column>=0&&column<grid[row].length)
			if(grid[row][column]==1)
				result=true;
		return result;
	}
	public String toString(){
		String result="
";
		for (int row=0;row<grid.length;row++){
			for(int column=0;column<grid[row].length;column++){
				result +=grid[row][column]+" ";
			}
			result+="
";
		}
		return result;
	}
	public static void main (String []args){
		Maze maze=new Maze();
		System.out.println(maze);
		if(maze.traverse(0, 0))
			System.out.println("The maze was successfully travelled!");
		else
			System.out.println("There is no possible path.");
		System.out.println(maze);
	}

}

9 연 결 된 조작 이 하나 더 있 습 니 다.관심 이 있 으 면 같이 보 세 요자바 재 귀 9 연쇄 문제 해결
총결산
자바 의 간단 한 재 귀 작업 실현 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 자바 재 귀 작업 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!