재귀 함수를 꼬리 재귀로 변환

Question

순환 이중 연결리스트에서 값 20을 갖는 모든 노드를 계산하는 다음 재귀 함수가 있습니다. 안전 문제를 방지하기 위해 이것을 꼬리 재귀 함수로 변환해야합니다. 같은 것을 도와주세요. 감사합니다

이 일반적으로 그렇게 실제로 도움이되지 않습니다 꼬리 재귀 형태로 기능을 번역, 꼬리 재귀를 인식하지 못하는 C. C 구현과 같은

int count(node *start) 
{ 
    return count_helper(start, start); 
} 
int count_helper(node *current, node *start) 
{ 
    int c; 
    c = 0; 
    if(current == NULL) 
     return 0; 
    if((current->roll_no) == 20) 
     c = 1; 
    if(current->next == start) return c; 
    return (c + count_helper(current->next, start)); 
} 

Answer 1

. iterative으로 변경해야합니다.

Answer 2

비 꼬리 재귀 함수를 꼬리 재귀 함수로 변환하는 일반적인 방법은 재귀 호출을 통해 현재 평가를 전달하는 여분의 누적 매개 변수를 사용하는 것입니다. 귀하의 경우에는

이 오히려 솔직하다 :

int count(node *start) 
{ 
    return count_helper(start, start, 0); 
} 
int count_helper(node *current, node *start, int acc) 
{ 
    int c; 
    c = 0; 
    if(current == NULL) 
     return acc; 
    if((current->roll_no) == 20) 
     c = 1; 
    if(current->next == start) return acc + c; 
    return count_helper(current->next, start, acc + c); 
} 

내가 여기했습니다 반환 문을 모두 당신의 count_helper 정의에 추가 누적 매개 변수 int acc를 추가하고 확인하고 있습니다 주요 변경 acc (해당하는 경우)을 포함하십시오. 이제 최종 return 문은 수정하지 않고 count_helper의 결과를 직접 전달합니다. 이것은 지금 tail-recursive입니다.

재귀 호출의 결과가 단순한 산술이 아닌 방식으로 결합되어야하는 경우는 덜 간단합니다.

그러나 ruakh이 언급했듯이 많은 C 컴파일러는 tail-recursive call을 최적화하는 데 어려움을 겪고 싶지 않습니다. 간단히 C 스타일이 아니기 때문입니다. 어쩌면 -O3 할 것인가?