재귀 함수가 넘쳐 흐릅니다. 그 이유는 무엇입니까?

Question

아래의 기능이 넘쳐 나는 이유를 모르겠다. x를 0으로, y를 0으로, dim를 2로 설정하면 결과는 6이되어야합니다. 그러나 오버 플로우가 발생할 때 함수의 x 또는 y 중 일부 Long 값이 554임을 나타내는 오류가 발생합니다. 두 곳에서

def lattice(dim: Long, x: Long, y: Long): Long = { 
    if (x == dim && y == dim) { 
    1 
    } 
    if (x >= dim) { 
    lattice(dim,x,y+1L) 
    } 
    if (y >= dim) { 
    lattice(dim,x+1L,y) 
    } 
    else { 
    lattice(dim,x+1L,y) + lattice(dim,x,y+1L) 
    } 
} 

Answer 1

당신은 else 누락 : x와 y가 모두 내 테스트에서 코드를 여기에 2 로 설정되어 희미한 값에 의해 제한되므로이 가능하지 않을 것이다. 즉, x >= dim 일 때 최종 라인이 실행되어 x가 dim을 초과하게됩니다. 대신이 시도 :

if (x == dim && y == dim) { 
    1 
} else if (x >= dim) { 
    lattice(dim,x,y+1L) 
} else if (y >= dim) { 
    lattice(dim,x+1L,y) 
} else { 
    lattice(dim,x+1L,y) + lattice(dim,x,y+1L) 
} 

Answer 2

크리스 :

youd가 기능이 꼬리 재귀되지 않기 때문에 마지막 문에 당신은 합이있다. 우연히이 합계에는 lattice에 대한 두 건의 호출이 포함됩니다. 그러나 꼬리 재귀가되기 위해서는 마지막 스테이트먼트가 상수가되어야합니다 (예 : if). 또는 함수 자체를 호출해야합니다 (예 :).

나는 어떻게해야 좋을지 모르겠다. 당신의 기능을 변경하는 것은 꼬리 재귀 할 수 있습니다. 당신의 alghoritm의 따라, 아마도 함수 꼬리 재귀를 할 수 없습니다.

감사합니다,

라파엘 아폰소