자바에서 재귀의 개념을 이해하는 방법?

Question

저는 자바 프로그래밍을 처음 접했고 선생님은 우리에게 재귀 개념을 가르쳐 주었고 조금 복잡했습니다. 나는 그것이 루프 (4의 계승과 같음)처럼 작동한다는 것을 이해했지만, 왜 아직도 그렇게 작동하는지 이해하지 못한다. 이 주제에 대한 자세한 설명을 볼 수 있습니까? 여기에 선생님이 설명했던 코드와 그림이 있습니다. 다음 이미지에서

package javaapplication1; 

public class JavaApplication1 { 

static int factorial(int n){ 
    int t; 
    if(n == 0){ 
     return 1; 
    } else { 
     t = factorial(n - 1); 
     return n * t; 
    } 
} 
public static void main(String[] args) { 
    System.out.println(factorial(5)); 
    } 
} 

파란색 색상 스택 권선 나타내며, 녹색 스택 해제되고, 다시 나는 감기 스택 모르는 및 청산입니다. 하나는 작업이 유사한 작은 작업으로 분류 될 수 있음을 알고 때 (우리가 특정 조건을 충족 할 때까지)

http://i.stack.imgur.com/pjqJy.png

Answer 1

재귀 함수는 return 문에 도달 할 때까지 자체를 호출하여 함수 자체를 호출하지 못하도록하는 함수입니다. 귀하의 모범을 보자. Factorial은 그 자체로 곱해진 숫자를 반환하는 수학 함수입니다. 1을 곱한 값 2, 1에 1을 곱한 값 예 : 5의 계승 값 = 5! = 5x4x3x2x1 = 120. 또한 자체의 계승 곱하기 -1과 동일합니다. = 5x4! 0을 고려하십시오! = 1 Java 코드에서이를 나타 내기 위해서는 1부터 시작하는 숫자를 곱하고 그 계승을 계산하는 숫자까지가는 루프가 필요합니다. 코드를 더 자세히 설명하면 Factorial (5)을 계산해 보겠습니다. Factorial()은 정수를 반환합니다.

main() : 5! = 0의 초기 호출에서 조건 (n == 0)을 건너 뜁니다. t = 요인 (5-1) = 요인 (4);

Factorial (4) : 4! = 0에서 두 번째 호출을 한 다음 조건 (n == 0)을 건너 뜁니다. t = 요인 (4-1) = 요인 (3);

세 번째 호출은 Factorial (3) : 3! = 0이고, 그런 다음 조건 (n == 0)을 건너 뜁니다. t = 요인 (3-1) = 요인 (2);

Factorial (2)에서 4 번째로 올린 전화 : 2!= 0이면 조건 ​​(n == 0)을 건너 뜁니다. t = 요인 (2-1) = 요인 (1);

Factorial (1) : 1! = 0에서 다섯 번째로 호출 한 다음 조건 (n == 0)을 건너 뜁니다. t = 요인 (1-1) = 요인 (0);

여섯 번째 호출은 Factorial (0)입니다. 0 == 0, then return value 1;

다섯 번째 호출 (Factorial (1))의 첫 번째 반환 값 : return n * t = return 1 * 1 = 반환 값 1;

두 번째 리턴, 1에서 네 번째 호출 (Factorial (2)) : return n * t = return 2 * 1 = 리턴 값 2;

세 번째 호출 (Factorial (3)) : return n * t = return 3 * 2 = 반환 값 6;

두 번째 호출 (Factorial (4))의 두 번째 반환 값 : return n * t = return 4 * 6 = 반환 값 24;

첫 번째 호출 (Factorial (5))에서 두 번째 반환, return n * t = return 5 * 24 = 반환 값 120;

초기 호출 (main()에서)으로 두 번째 반환, 120 : print (120);

희망 사항은 재귀를 이해하는 데 도움이됩니다.

Answer 2

는, 우리는 재귀 또는 동일한 메소드를 호출을 사용합니다. Recursion 다른 메서드를 정의하거나 호출 할 필요없이 문제를 실행하는 데 도움이 될뿐만 아니라 작업이 실행되는 패턴을 시각화하는 데 도움이됩니다.

Answer 3

다른 메서드를 호출하면 스택 프레임이 만들어집니다 현재 메서드의 상태를 유지하고 스택에 푸시됩니다. 이는 자체 또는 다른 메소드를 호출하는 메소드와는 관계가 없습니다.

호출이 돌아 오면 스택 프레임이 스택에서 팝되고 메서드의 상태가 복원되며 호출 메서드에서 실행이 계속됩니다.

재귀는 메서드가 (직접 또는 간접적으로) 자신을 호출하는 경우입니다. 재귀 적 방법의 일반적인 형태는 다음과 같다 : 매개 변수가 종료 조건, 반환 (보통 결과) 그렇지

코드 자체

다음 반복에 대한 매개 변수를 조정하고 전화를 충족

• 경우 선생님이 쓴 글에는 스타일에 관한 몇 가지 문제가 있습니다.

  I - (단지 실행 계속 거기가 반환 "경우"에는 "다른 사람"없음) 불필요한 변수 t 중복 else을 근절

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

  : 다음과 같이 기록 된 경우는 명확 것 그것을 설명하는 경우

  static int factorial(int n) { 
      return n == 0 ? 1 : n * factorial(n - 1); 
  } 
  

Answer 4

나는 잘 모르겠지만, 당신이 precalculus 클래스가 있다면 당신은 그 계승은 두 waqys 정의 할 수 있습니다 알고 있어야 다음 if 모두 제거, 이런 식을 작성합니다.

N! = 1 * 2 * ... * N

우리

정의 1의! = 1

및

N! = N * (N-1) !

해당 정의가 동일한 지 확인하십시오. 우리가 말하게하자, 5!

제 2 정의에 따른

5! = 5 * 4!

그러나 4! = 4 * 3! 그래서 5! = 5 * 4 * 3!

그러나 3! = 3 * 2! 그래서 5! = 5 * 4 * 3 * 2!

등등. 당신이 1을 칠 때까지 그것을 계속해라!. 하지만 1! = 1 그래서 당신은 멈 춥니 다.

프로그래밍에서 반복은 동일한 것입니다.

TomW

Answer 5

개인적으로 나는 계승 문제를 좋아하지 않습니다. 나는 이해하기가 어려워서 명확한 방법으로 재귀를 설명한다고 생각하지 않는다. 그래서 다른 예를 살펴 보겠습니다. 1-100의 숫자를 인쇄하려고합니다. 이것은 for 루프와 카운터를 사용하는 매우 간단한 작업이지만 재귀를 사용하여 수행 할 수도 있습니다. 예 :

public static void main(String[] args) { 
    numbersAscending(1); 
    numbersDescending(1); 
} 
//Prints 1 2 3 ... 100 
public void numbersAscending(int x){ 
    System.out.println(x); 
    if(x < 100){ 
     numbersAscending(x+1); 
    } 
} 
//Prints 100 99 98 ... 1 
public void numbersDescending(int x){ 
    if(x < 100){ 
     numbersDescending(x+1); 
    } 
    System.out.println(x); 
} 

함수가 호출되면 해당 호출이 스택 맨 위로 이동합니다. 이것을 카드 더미처럼 생각하십시오. 각자 그것에 번호가 있습니다 (1-100). 함수가 자신을 호출하면 새 카드가 스택에 추가됩니다. 함수가 완료되면 스택에서 제거됩니다.

위 예제에서 numbersAscending이 호출 될 때마다 해당 함수를 다시 호출하기 전에 x의 현재 값을 인쇄합니다. 결과는 1-100 순서로 인쇄됩니다. 100에 도달하자마자, 스택은 자신을 호출하는 것을 멈추고 스택에서 각 기능을 끕니다.

numbersDescending이 호출 될 때마다 숫자를 인쇄하기 전에 다시 호출합니다. 이렇게하면 x는 100에 도달 할 때까지 인쇄를 시작하지 않습니다. 그런 다음 스택을 아래로 이동하여 각 번호가 기본 방법으로 돌아갈 때 인쇄합니다.