재귀 통화에서 무한 루프를 감지하는 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/1030527

  •  06-07-2019
  •  | 
  •  

문제

재귀 적으로 스스로를 호출하는 함수가 있으며, 무한 루프로 들어가면 탐지하고 종료하고 싶습니다. 즉, 다시 같은 문제를 요구합니다. 가장 쉬운 방법은 무엇입니까?

편집 : 이것은 기능이며 x와 y의 다른 값으로 재귀 적으로 호출됩니다. 재귀 호출에서 쌍 (x, y)의 값이 반복되면 종료하고 싶습니다. 

int fromPos(int [] arr, int x, int y)
도움이 되었습니까?

해결책

함수가 순전히 기능적이라면 상태 또는 부작용이 없으면 Set 인수 중 (편집 : 편집을 볼 수 있으면, 당신은 그것이 호출 된 (x, y)의 쌍을 유지하고, 매번마다 현재 인수가 세트에 있는지 확인하십시오. 그렇게하면 사이클이 꽤 빨리 달리면 사이클을 감지 할 수 있습니다. 그러나 인수 공간이 크고 반복되는 데 시간이 오래 걸리면 사이클을 감지하기 전에 기억이 떨어질 수 있습니다. 물론 일반적으로 이것은 중단 문제이기 때문에 할 수 없습니다.

다른 팁

한 가지 방법은 전달하는 것입니다 depth 한 통화에서 다음 호출로 변수로 기능을 호출 할 때마다 증가합니다. 확인하십시오 depth 특정 임계 값보다 더 크게 자라지 않습니다. 예시:

int fromPos(int [] arr, int x, int y)
{
    return fromPos(arr, x, y, 0);
}

int fromPos(int [] arr, int x, int y, int depth)
{
    assert(depth < 10000);

    // Do stuff

    if (condition)
        return fromPos(arr, x+1, y+1, depth + 1);
    else
        return 0;
}

요청대로 일반적인 해결책이 없기 때문에 작업 원을 찾아야합니다. 참조 중단 문제 더 많은 정보를 위해서.

쉬운 방법은 다음 중 하나를 구현하는 것입니다.

이전 값과 새 값을 재귀 콜에 전달하고 첫 번째 단계를 동일하게 확인하기 위해 확인하십시오. 이것은 아마도 재귀적인 케이스 일 수 있습니다.

변수를 전달하여 함수가 호출 된 횟수를 나타내고 호출 할 수있는 횟수를 임의로 제한합니다.

프로그램 분석을 사용하여 가장 사소한 것만 감지 할 수 있습니다. 당신이 할 수있는 최선은 특정 상황에 경비원을 추가하고 깊이 수준 컨텍스트를 통과하는 것입니다. 일반적인 사례를 감지하고 재귀 알고리즘의 합법적 인 사용을 차별화하는 것은 거의 불가능합니다.

일관된 서명을 위해 과부하를 사용하거나 (더 나은 방법) 정적 변수를 사용할 수 있습니다.

int someFunc(int foo)
{
    static recursionDepth = 0;
    recursionDepth++;
    if (recursionDepth > 10000)
    {
        recurisonDepth = 0;
        return -1;
    }
    if (foo < 1000)
        someFunc(foo + 3);
    recursionDepth = 0;
    return foo;
}

오버로드에 대한 John Kugelman의 답변은 스레드가 안전하지만 정적 변수는 그렇지 않습니다.

빌리 3

2D 배열에서 작업하는 것 같습니다. 배열 값에서 여분의 비트가 있다면 플래그로 사용할 수 있습니다. 그것을 확인하고 플래그가 설정된 경우 재귀를 종료하십시오. 그런 다음 계속하기 전에 설정하십시오.

값에서 약간의 여유가 없으면 대신 객체 배열로 만들 수 있습니다.

메소드 서명을 유지하려면 x와 y의 오래된 값을 기록하기 위해 몇 세트를 유지할 수 있습니다.

static Set<Integer> xs;
static Set<Integer> ys;//Initialize this!
static int n=0;//keeps the count function calls.

int fromPos(int [] arr, int x, int y){

 int newX= getX(x);
 int newY= getY(y);
 n++; 
 if ((!xs.add(Integer.valueOf(newX)) && !ys.add(Integer.valueOf(newY))){

   assert(n<threshold); //threshold defined elsewhere.
   fromPos(arr,newx,newy);
 }
}

IMHO 전용 루프는 무한 루프로 들어갈 수 있습니다.

방법에 재귀 수준이 너무 많으면 JVM은 stackoverflowerror를 던질 것입니다. 시도/캐치 블록 으로이 오류를 가두고이 조건이 발생할 때 수행하려는 모든 일을 수행 할 수 있습니다.

재귀 함수는 조건이 충족되는 경우 종료됩니다.

예 :

  • 함수의 결과는입니다 0 또는입니다 1
  • 최대 통화 수에 도달합니다
  • 결과는 입력 값보다 낮거나 큽니다.

귀하의 경우 조건이 있습니다 ([x0,y0] == [xN,yN]) OR ([x1,y1] == [xN,yN]) OR ([xN-1,yN-1] == [xN,yN])

0, 1, ...N 쌍의 인덱스입니다

따라서 모든 이전 쌍을 저장하고 현재 쌍과 비교하려면 컨테이너 (벡터, 목록,지도)가 필요합니다.

먼저 MVN FindBugs : GUI를 사용하여 GUI를 열어이 오류가있는 선을 가리 킵니다.

나는 또한 같은 문제에 직면했으며 루프 검증에 부울 변수를 추가하여 해결했습니다.

이전 ->

for (local = 0; local < heightOfDiv; local = local + 200) { // Line under Error
          tileInfo = appender.append(tileInfo).append(local).toString();
          while (true) {
            try {
              tileInfo = appender.append(tileInfo).append(getTheTextOfTheElement(getTheXpathOfTile(incr))).toString();
              incr++;
            } catch (Exception e) {
              incr = 1;
              tileInfo = appender.append(tileInfo).append("/n").toString();
            }
          }

이 문제를 해결하기 위해 부울 변수를 추가하여 캐치 블록에서 False로 설정했습니다. 확인하십시오 

for (local = 0; local < heightOfDiv; local = local + 200) {
          tileInfo = appender.append(tileInfo).append(local).toString();
          boolean terminationStatus = true;
          while (terminationStatus) {
            try {
              tileInfo = appender.append(tileInfo).append(getTheTextOfTheElement(getTheXpathOfTile(incr))).toString();
              incr++;
            } catch (Exception e) {
              incr = 1;
              tileInfo = appender.append(tileInfo).append("/n").toString();
              terminationStatus = false;
            }
          }

이것이 내가이 문제를 해결하는 방법입니다. 이것이 도움이되기를 바랍니다. :)

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top