재귀 메서드 호출의 순서

Question

jvm에서 재귀가 어떻게 작동하는지 궁금합니다. 예제를 따르십시오. 주어진 숫자의 첫 번째 계승 계산.

public class Factorial { 

public int factorial(int n) { 
    System.out.println("Factorial: " + n); 
    if (n < 2) { 
     return 1; 
    } 

    return n * factorial(n - 1); 
} 

다음 테스트를

@Test 
public void test_factorial() { 
    Factorial fact = new Factorial(); 
    System.out.println(fact.factorial(3)); 
} 

표시

3 
2 
1 

실행 그리고 그것은 분명한 것 같다, 메서드 호출 스택에 배치됩니다, 실행은 n 개의 == 1에 도달하며 돌아갑니다. 이제 fibonacci 숫자를 계산하려고했습니다.

public int fibo(String name, int n) { 
    System.out.println("fibo: " + name + " " + n); 
    if (n < 2) { 
     return n; 
    } 
    return fibo ("left", n - 1) + fibo ("right", n - 2); 
} 

테스트 실행

@Test 
public void test_fibonacci() { 
    Fibo fibo = new Fibo(); 

    assertEquals(8, fibo.fibo("start",6)); 

} 

다음 무엇을 인쇄

fibo: start 6 
fibo: left 5 
fibo: left 4 
fibo: left 3 
fibo: left 2 
fibo: left 1 
fibo: right 0 
fibo: right 1 
fibo: right 2 
fibo: left 1 
fibo: right 0 
fibo: right 3 
fibo: left 2 
fibo: left 1 
fibo: right 0 
fibo: right 1 
fibo: right 4 
fibo: left 3 
fibo: left 2 
fibo: left 1 
fibo: right 0 
fibo: right 1 
fibo: right 2 
fibo: left 1 
fibo: right 0 

내 질문 메소드를 호출하고이 예에서 스택에 넣어의 규칙은 무엇입니까?

Answer 1

문장은 Java에서 왼쪽에서 오른쪽으로 평가됩니다. 다음은 작은 입력에 대한 피보나치 함수의 간단한 분석입니다 :

fib.fibo("start",3) 

이 호출되면서 "start : 3"이 출력됩니다. 그것은이

(2) fibo("left", 2) 

가 먼저 평가됩니다 것을 의미, 평가 LTR 때문에

(1) fibo("left", 2) + fibo("right", 1) 

을 평가하려고합니다. 우리는 새로운 스택 프레임을 만들고 statement (1)은 반환을 기다리고 있습니다. 우리는

(4) fibo("left", 1) 

첫번째 평가

(3) fibo("left", 1) + fibo("right", 0) 

가 다시, LTR 평가의 의미 평가하려고 : 호출 (2) 인쇄는 "2 왼쪽". 다시, 새로운 스택 프레임, (3)은 (4)의 응답을 기다립니다.

(5) fibo("right", 0) 

이 인쇄 호출과 1 스택 프레임 팝을 반환하고, (3) 지금은 평가를 계속 "오른쪽 : 0"과 0 (2)입니다 반환 (4) 인쇄는 "1"왼쪽 호출 (1)은 마침내 fibo("left", 2)의 평가를 마쳤으며 위와 같은 방법으로 fibo("right",1)을 계속 평가할 수 있습니다.

이 내용이 명확하게 설명되기를 바랍니다.

Answer 2

무엇이 문제입니까? 당신은 (Left 1은 내부 Right 2있다)이 코드를 실행하는 동안 오른쪽 또는 왼쪽으로 왼쪽에서 오른쪽으로 변경 :

이

   start 
    left1   right1 
left2 right2 left3 right3 

당신이 먼저 left1, left2를 호출합니다. 그런 다음 왼쪽 1로 돌아가서 인쇄하지 않고 right2으로 전화하십시오. 그런 다음 두 번 돌아 오면 다시 start에 있습니다.그 후에 right1으로 전화하면 유사합니다.

그래서 당신은 : 시작 - Left 1 - left2 - Right 2 - 한 Right - left3 - right3 현실 세계에서