홈>2020-02-01 01:27

algorithm - 재귀를 사용하여 목록의 첫 번째 요소와 마지막 요소 찾기

Scala에서 재귀 함수를 작성하여 목록의 첫 번째 요소와 마지막 요소를 반환하려고합니다 (쌍). .head 만 사용하고 싶습니다 그리고 .tail match 없이 간단한 (꼬리가 아닌) 재귀를 사용합니다 (추가 기능을 정의하지 않고). 가능합니까?

이 코드를 사용하여 찾을 수있는 마지막 요소 :

def foo(x: List[Int]): (Int) = {
    if (x.tail.isEmpty) (x.head)
    else foo(x.tail)
}

첫 번째 요소와 마지막 요소 (Int, Int) 와의 쌍을 반환하고 싶습니다 . 매개 변수는 (x: List[Int]) 입니다 . 내가 head 를 통과하면 쉽습니다 매개 변수로 사용하지만 수행하지 않고도 가능합니까?

답변 # 1
꼬리에는 안쪽의 재귀 함수를 사용할 수 있고 머리에는 바깥 쪽 함수를 사용할 수 있습니다.

그러나 이것이 여전히 운동의 정신에 있는지 여부는 또 다른 질문입니다.

다음은 매우 비효율적 인 솔루션입니다.
```
def firstAndLast (list: List[Int]): (Int, Int) = {
  if (list.isEmpty) (0, 0) 
  else if (list.size == 1) (list.head, list.head) 
  else if (list.size == 2)
     (list.head, list.tail.head)
  else
    firstAndLast (list.head :: list.tail.tail)
}
```
헤드를 별도의 매개 변수로 전달하지 않고 2보다 긴 경우 나머지 나머지 헤드의 헤드에 다시 추가합니다.

빈 케이스에 대한 의미있는 리턴을 위해 나는 좋은 생각이 없었다. 일반적으로 튜플의 반환 옵션은 방법입니다.

답변 # 2

다른 접근법

def headTail(l:List[Int]) : (Int, Int) = {
  if(l.isEmpty) (-1, -1)
  else if(l.tail == List())  (l.head, -1)
  else if(l.tail.tail.isEmpty)  (l.head, l.tail.head)
  else headTail(l.head :: l.tail.tail) //eliminates second element for every iteration
}

Python2.net

algorithm - 재귀를 사용하여 목록의 첫 번째 요소와 마지막 요소 찾기

관련 자료