반복 메소드를 반복 메소드로 변경하는 방법

Question

아래의 메소드를 반복에서 재귀로 변경하는 방법은 무엇입니까?

public int[] pascal(int[] previous) 
{ 

    //The row is 1 element longer than previous row 
    int[] row = new int[previous.length + 1]; 

    //The first and last numbers in row are always 1 
    row[0] = 1; 
    row[row.length - 1] = 1; 

    //The rest of the row can be calculated based on previous row 
    for (int i = 1; i < row.length-1; i++) 
    { 
     row[i] = previous[i-1] + previous[i]; 
    } 

    return row; 
} 

Answer 1

"상태"는 매개 변수를 통해 전달되어야합니다. 따라서 int[] previous 행보다 많은 매개 변수가 필요합니다.

일반적으로 두 가지 방법, 즉 더 간단한 인터페이스를 사용하는 공개 방법과 실제 계산을 수행하는 개인 방법 중 하나를 원합니다. 계산되는 새로운 행으로 계산해야 다음 위치의 인덱스를 통과하는 것이 가장 간단한 방법

public int[] pascal(int[] previous) { ... call the next overload ... } 
private int[] pascal(... all the state needed ...) { ... recursive call or return the value ... } 

하나 : 당신의 예에서

,이 두 가지 방법은 다음과 같을 것 재귀 함수의 매개 변수 그래서, 당신은 가질 것이다 :

private int[] pascal(int[] previous, int currentIndex, int[] row) { ... } 

자, 재귀 함수는 일반적으로 2 (또는 그 이상)의 경우가 있습니다. 은 "currentIndex는"당신은, 우리가 완료 계산해야 마지막 인덱스 과거의 경우

• - 그것은 지금처럼 단지 행을 반환;이 들어, 두 개의 사례를해야합니다
• 그렇지 않으면 현재 색인의 값을 계산하여 행에 넣고 계산을 계속할 재귀 호출을 만듭니다 (완료 여부를 결정하거나 다시 계산하고 다시 호출하여 ...).)

하자 코드이 2가지 경우 :

private int[] pascal(int[] previous, int currentIndex, int[] row) { 
    if (currentIndex == previous.length) { 
    return row; 
    } else { 
    // do some part of the calculation 
    // and make a recursive call that would continue the calculation: 
    return pascal(previous, ????, row); 
    } 
} 

이 재귀 함수의 구조를 왜 보는가?

좋아, 실제 계산에 :

private int[] pascal(int[] previous, int currentIndex, int[] row) { 
    if (currentIndex == previous.length) { 
    return row; 
    } else { 
    int currentValue = previous[currentIndex - 1] + previous[currentIndex]; 
    row[currentIndex] = currentValue; 
    return pascal(previous, currentIndex, row); 
    } 
} 

계산은 이루어집니다. 지금 당신은 당신의 "간단하게"기능이 적절한 매개 변수와 재귀 함수를 호출 할 필요가 : 그것 뿐이다

public int[] pascal(int[] previous) { 
    int rowSize = previous.length + 1; 
    int[] row = new int[rowSize]; 
    row[0] = 1; 
    row[rowSize - 1] = 1; 
    return pascal(previous, 1, row); 
} 

합니다.

"트릭"은 매개 변수에 "상태"를 유지하는 것입니다. 여기에서 currentIndex은 원래 for 루프에 int i과 같습니다.

Answer 2

지금 프로그래밍되었으므로 원하는 것을 얻기 위해 여러 번 함수를 호출해야합니다.

재귀 함수는 자체를 호출합니다. 이 방법은 한 번만 호출하면 원하는 것을 얻을 수 있습니다.

삼각형의 특정 행 하나만 필요하다고 가정합니다. 함수에 전달해야하는 유일한 매개 변수는 행 번호입니다.

이미 함수가 프로그래밍되어 있고 특정 행 번호 N-1로 호출 할 수 있다고 상상해보십시오. 이전 행을 사용하여 행 N을 계산하는 함수를 작성할 수 있습니까?

이제 첫 번째 행과 음수 행 번호의 경우를 처리하십시오.

즉,이 함수를 사용하여 삼각형 행을 행별로 표시하는 것은 매우 비효율적입니다.