스칼라 : 재귀 적으로 배열의 최대 값을 찾습니다.

Question

저는 scala를 처음 사용했습니다. 재귀를 연습하기 위해 필자는 배열의 최대 값을 찾는 작업을 스스로했습니다. 내 기본 케이스는 길이가 1 인 배열입니다. 각 재귀 패스에 대해 배열 값 0과 1의 크기를 비교하여 기본 케이스가 충족 될 때까지 더 작은 값을 제거합니다.

def max(m: Array[Int]): Int = { 
     if (m.length == 1) m(0) 
     else if (m(0) > m(1)) m.take(1) 
     else m.take(0) 
    return max(m) 
    } 

그러나 repl에서는 아무 것도 반환하지 않습니다 (아마 무한 루프). 배열이 길이 1로 줄어들지 않는 이유를 모르겠습니다. 보조 내부 함수가 필요합니까?

Answer 1

이 확실히 무한 루프 (전문 용어로, take는 수정되지 않습니다).

나머지 질문에 대답하려면 에 내부 도우미 기능이 필요합니다.

봅니다 스칼라에 다음과 같은 알고리즘을 번역하기 : 목록이 비어

• 경우, 오류 그밖에 ​​
• 을 던져 목록은 그렇지
• 의 첫 번째 요소 반환 하나 개의 요소가있는 경우
  • (재귀 적으로) 최대 값 m.take(1)을 계산하려면 max_of_rest
  • 큰 것을 반환하십시오. m(0) 및 max_of_rest

스칼라 재미 학습 재귀 되세요!

ADDENDUM

상기 알고리즘은 정답을 생성하면서, 매우 비효율적으로한다. 고려하십시오 :

maximum([2, 4, 1, 10, 3]) 
    = max(2, maximum([4, 1, 10, 3])) 
    = max(2, max(4, maximum([1, 10, 3]))) 
    = max(2, max(4, max(1, maximum([10, 3])))) 
    = max(2, max(4, max(1, max(10, maximum([3]))))) 
    = max(2, max(4, max(1, max(10, 3)))) 
    = max(2, max(4, max(1, 10))) 
    = max(2, max(4, 10)) 
    = max(2, 10) 
    = 10 

각 호출이 호출 스택에서 "쌓여"많은 추가 메모리를 소비하는 점에 유의하십시오. 이 경우 tail-recursive 공식을 사용하는 것이 훨씬 더 좋습니다. 주스트 덴 보어에 의해 지적

maximum([2, 4, 1, 10, 3]) 
    = _maximum([4, 1, 10, 3], max(4, 2)) 
    = _maximum([1, 10, 3], max(1, 4)) 
    = _maximum([10, 3], max(10, 4)) 
    = _maximum([3], max(3, 10)) 
    = _maximum([], 10) 
    = 10 

지금이 꼬리 재귀 경우에, 당신은 두 번째 기능이 수행 .이 내부 재귀 함수는 외부 함수는 당신이 그것을 운동을 즐길 수 있도록 내가 스칼라 구문을 사용하여 의도적 아니에요

maximum(a) = 
    if a is empty raise an error 
    else return _maximum(a.take(1), a(0)) 

같은 것을 진행이

_maximum(a, v) = 
    if a is empty return v 
    else return _maximum(a.take(1), max(a(0), v)) 

처럼 작동하는지 확인할 수 있습니다. 재미있어!

Answer 2

m.take()m을 수정하지 않습니다. 결과적으로 동일한 배열을 인자로 계속 반복해서 사용하여 max(m)을 호출하게됩니다.

scala> val m = Array(1, 2, 3, 4, 5); 
m: Array[Int] = Array(1, 2, 3, 4, 5) 

scala> m.take(1) 
res0: Array[Int] = Array(1) 

scala> m 
res1: Array[Int] = Array(1, 2, 3, 4, 5) 

또한 take() 전혀 당신이하고있는 생각하지 않는 것을 알 수 있습니다. 당신이 반복적으로 당신이 전달 같은 인수 max를 호출로

scala> m.take(0) 
res2: Array[Int] = Array() 

scala> m.take(3) 
res3: Array[Int] = Array(1, 2, 3)