처음 실행될 때 재귀가 작동하는 방식

Question

sub maxNum { 
if (@_ == 1) { 
    return $_[0]; # terminal clause - return immediately 
} 
my ($first, @rest) = @_; 
my $remainingMax = maxNum(@rest); 
    if ($first > $remainingMax) { 
    return $first; 
    } 
return $remainingMax; 
} 

재귀를 사용하는이 코드 조각을 처리하는 데 문제가 있습니다. 기본적으로 나는 my $remainingMax = maxNum(@rest); 부분으로 혼란스러워합니다.

스크립트가 나는 기능 maxNum(@rest)가 ANS (즉, 하나 return $first 또는 return $remainingMax)를 반환하여 값을 제공한다는 것을 이해하고, 그 후에 매우 처음으로에 대해 실행될 때 난 그냥 $remainingMax의 값이 발견 방법을 알고 싶어요

.

Answer 1

귀하의 혼란을 이해하지 못합니다.

처음으로 maxNum이 완료되면이 목록의 마지막 항목을 반환합니다.

이제 마지막 두 항목의 목록을 생각해 보면 해당 항목을 전달하면 $first이되고 다른 하나는 @rest에 할당 된 유일한 요소가됩니다. @rest을 하나의 요소로 전달하면 터미널 조건에 도달하고 해당 요소가 반환되어 $remainingMax에 저장됩니다. 마지막 두 요소를 비교하여 최대 요소를 반환합니다.

두 개의 항목보다 큰 목록으로 원래 maxNum을 호출 한 경우 반환 된 최대 항목을 목록 끝에있는 세 번째 항목 (Perl 하위 문자 -3)과 비교하십시오. 그것이 총 목록이라면, 당신은 당신의 최대 목록을 가지고 있습니다. 그렇지 않은 경우이를 반환하고 마지막 (Perl 첨자 -4)의 네 번째 항목과 비교합니다. 준 "펄 표기"

maxNum($_[-1])  ==> $_[-1]; 
maxNum($_[-2..-1]) ==> $_[-2] > maxNum($_[-1])  ? $_[-2] : maxNum($_[-1]); 
maxNum($_[-3..-1]) ==> $_[-3] > maxNum(@_[-2..-1]) ? $_[-3] : maxNum(@_[-2..-1]); 
maxNum($_[-4..-1]) ==> $_[-4] > maxNum(@_[-3..-1]) ? $_[-4] : maxNum(@_[-3..-1]); 
... 

Answer 2

재귀 함수는 일반적으로 "분할 정복을"을 수행 -strategy에서

.

<=> max(max(a, b), max(c, d)) 

귀하의 알고리즘은 다음 파티션 선택 :

임의로, 모든 지역 최대의 최대 값을 찾아 우리가 그 목록을 분할 할 수

max(a, b, c, d) 

목록의 최대를 찾으려면

<=> max(a, max(b, c, d)) 

max(b, c, d)에 대해서도 마찬가지입니다. 호출 그래프 :

max(a, b, c, d) 
    max(b, c, d) 
     max(c, d) 
     max(d) 

max(d)에서 알고리즘은 더 이상 발생하지 않습니다. 대신 기본 사례 (루프의 종료 조건에 해당)입니다. max(d)은 d을 반환합니다. 우리는 지금이 아이디어는 인코딩 할 수있는 다른 많은 방법이있다

---

호출 스택을 통해 다시 우리의 방식으로 작동합니다, 우리의 첫 번째 값에리스트의 나머지의 최대 값을 비교하여 총 최대를 찾을 수 있습니다.

sub maxNum { 
    my $current_max = pop; 
    while(@_) { 
    my $compare = pop; 
    $current_max = $compare if $compare > $current_max; 
    } 
    return $current_max; 
} 

이렇게하면 재귀 적 솔루션과 같은 순서로 요소를 비교합니다.

최대 값을 찾는 것은 접기 작업 (일명 reduce)으로 간주 할 수 있습니다. 우리는 다음과 같은 파티션 않는 재귀 함수를 쓸 수 있습니다 :이 은 매우 복잡 보이는

max(a, b, c, d) 
<=> max(max(a, b), c, d) 
<=> max(max(max(a, b), c), d) 

을하지만 우아한 해결책에 이르게 : 값이 즉시이라고한다 반환

sub maxNum { 
    return $_[0] unless $#_;  # return if less than two elems 
    my ($x, $y) = splice 0, 2, @_; # shift first two elems from @_ 
    my $max = $x > $y ? $x : $y; # select larger 
    return maxNum($max, @_);  # recurse 
} 

함수 호출 꼬리 전화. 특별한 goto &subroutine 표현식을 사용하여 더 효율적으로 만들 수 있습니다. 그러나 인수 목록을 수동으로 설정해야합니다.

sub maxNum { 
    return shift unless $#_;  # base case: return on one argument 
    my ($x, $y) = splice 0, 2, @_; # take the first two elems from start 
    unshift @_, $x > $y ? $x : $y; # put the larger one back there 
    goto &maxNum;     # recurse with tail call 
}