Konwertuj rekurencję normalną na rekurencję ogonową

Nie wiem jak teoretyczne jest to pytanie, ale rekurencyjna implementacja nie będzie skuteczna nawet z rekurencją ogonową. Spróbuj na przykład obliczyć pascal(30, 60). Nie wydaje mi się, że dostaniesz przepełnienie stosu, ale przygotuj się na długą przerwę na kawę.

Zamiast tego rozważ użycie Stream lub memoization :

val pascal: Stream[Stream[Long]] = 
  (Stream(1L) 
    #:: (Stream from 1 map { i => 
      // compute row i
      (1L 
        #:: (pascal(i-1) // take the previous row
               sliding 2 // and add adjacent values pairwise
               collect { case Stream(a,b) => a + b }).toStream 
        ++ Stream(1L))
    }))

Tak, to możliwe. Zwykle odbywa się to za pomocą wzorca akumulatora poprzez jakąś wewnętrznie zdefiniowaną funkcję, która ma jeden dodatkowy argument z tzw. logiką akumulatora, przykład z liczeniem długości listy.

Na przykład normalna rekurencyjna wersja wyglądałaby tak:

def length[A](xs: List[A]): Int = if (xs.isEmpty) 0 else 1 + length(xs.tail)

To nie jest rekurencyjna wersja ogona, aby wyeliminować ostatnią operację dodawania musimy gromadzić wartości, podczas gdy w jakiś sposób, na przykład z wzorem akumulatora:

def length[A](xs: List[A]) = {
  def inner(ys: List[A], acc: Int): Int = {
    if (ys.isEmpty) acc else inner(ys.tail, acc + 1)
  }
  inner(xs, 0)
}

Trochę dłużej kodować, ale myślę, że pomysł Rozumiem. Przyczyny można to zrobić bez wewnętrznej funkcji, ale w takim przypadku należy podać acc wartość początkową ręcznie.

Jestem prawie pewien, że jest to nie możliwe w prosty sposób, w jaki szukasz ogólnej sprawy, ale zależy to od tego, jak rozbudowane pozwolisz na zmiany.

Funkcja rekurencyjna ogona musi być ponownie zapisywalna jako pętla while, ale spróbuj zaimplementować na przykład fraktalne drzewo używając pętli while. Jest możliwe, ale trzeba użyć tablicy lub kolekcji, aby zapisać stan dla każdego punktu, który jest przechowywany dla danych przechowywanych w stos wywołań.

Możliwe jest również użycie trampoliningu .

Podejście akumulatorowe

  def pascal(c: Int, r: Int): Int = {

    def pascalAcc(acc:Int, leftover: List[(Int, Int)]):Int = {
      if (leftover.isEmpty) acc
      else {
        val (c1, r1) = leftover.head
        // Edge.
        if (c1 == 0 || c1 == r1) pascalAcc(acc + 1, leftover.tail)
        // Safe checks.
        else if (c1 < 0 || r1 < 0 || c1 > r1) pascalAcc(acc, leftover.tail)
        // Add 2 other points to accumulator.
        else pascalAcc(acc, (c1 , r1 - 1) :: ((c1 - 1, r1 - 1) :: leftover.tail ))
      }
    }

    pascalAcc(0, List ((c,r) ))
  }

Nie przepełnia stosu, ale jak na dużym wierszu i kolumnie, ale Aaron wspomniał, że nie jest szybki.

To jest rzeczywiście możliwe. / Align = "left" / zacznij od List (1) i kontynuuj rekursowanie aż do chcesz wiosłować. Warto zauważyć, że można go zoptymalizować: Jeśli c = = 0 lub c = = r wartość jest jedna, a aby obliczyć powiedzmy kolumnę 3 z 100 wiersza, nadal wystarczy obliczyć trzy pierwsze elementy poprzednich wierszy. Działającym rozwiązaniem rekurencyjnym ogona byłoby:

def pascal(c: Int, r: Int): Int = {
  @tailrec
  def pascalAcc(c: Int, r: Int, acc: List[Int]): List[Int] = {
    if (r == 0) acc
    else pascalAcc(c, r - 1,
    // from let's say 1 3 3 1 builds 0 1 3 3 1 0 , takes only the
    // subset that matters (if asking for col c, no cols after c are
    // used) and uses sliding to build (0 1) (1 3) (3 3) etc.
      (0 +: acc :+ 0).take(c + 2)
         .sliding(2, 1).map { x => x.reduce(_ + _) }.toList)
  }
  if (c == 0 || c == r) 1
  else pascalAcc(c, r, List(1))(c)
}

Adnotacja @tailrec faktycznie sprawia, że kompilator sprawdza funkcję jest rzeczywiście ogon rekurencyjny. Może być prawdopodobnie bardziej zoptymalizowany, ponieważ biorąc pod uwagę, że wiersze są symetryczne, Jeśli C > R/2, pascal ( c,r) == pascal (R-C,R).. ale pozostawione czytelnikowi;)