Разница между рекурсивным наибольшим общим девиатором и рекурсивным паскальским треугольником - PullRequest
Новая
       42

Разница между рекурсивным наибольшим общим девиатором и рекурсивным паскальским треугольником

0 голосов
/ 27 мая 2018

Может ли кто-нибудь объяснить мне, как эти две рекурсивные функции отличаются друг от друга?Я понимаю математический подход каждого из них, но я не понимаю, почему gcd () продолжает работать, пока не найдет gcd, но pascal () останавливается после одного раунда.Спасибо.

Величайший общий разработчик: 

def gcd(x: Int, y: Int): Int =
    if (y == 0) x else gcd(y, x % y)

Треугольник Паскаля 

def pascal(c: Int, r: Int): Int = {
      if(c < 0 || r < 0 ||  c > r) 0
      else if(c == 0 || r == 0) 1
      else pascal(c-1, r-1) + pascal(c, r-1)

  }

1 Ответ

0 голосов
/ 27 мая 2018

Вот ваш pascal -метод, дополненный несколькими отступами, для визуализации порядка выполнения вычислений: 

var currentIndentation = 0
def indenting[X](body: => X): X = {
  currentIndentation += 2
  val res = body
  currentIndentation -= 2
  res
}
def indentPrintln(s: String) = println(" " * currentIndentation + s)

def pascal(c: Int, r: Int): Int = {
  indentPrintln("pascal(%d, %d)".format(c, r))
  if(c < 0 || r < 0 ||  c > r) {
    indentPrintln("base case: return 0")
    0
  } else if(c == 0 || r == 0) {
    indentPrintln("base case: return 1")
    1
  } else indenting {
    val a = pascal(c-1, r-1)
    val b = pascal(c, r-1)
    val sum = a + b
    indentPrintln(
      "return sum pascal(%d, %d) + pascal(%d, %d) = %d + %d = %d"
      .format(c-1, r-1, c, r-1, a, b, sum)
    )
    sum
  }
}

println(pascal(3, 5))

Для (3, 5) он приводит к следующему выводу: 

pascal(3, 5)
  pascal(2, 4)
    pascal(1, 3)
      pascal(0, 2)
      base case: return 1
      pascal(1, 2)
        pascal(0, 1)
        base case: return 1
        pascal(1, 1)
          pascal(0, 0)
          base case: return 1
          pascal(1, 0)
          base case: return 0
          return sum pascal(0, 0) + pascal(1, 0) = 1 + 0 = 1
        return sum pascal(0, 1) + pascal(1, 1) = 1 + 1 = 2
      return sum pascal(0, 2) + pascal(1, 2) = 1 + 2 = 3
    pascal(2, 3)
      pascal(1, 2)
        pascal(0, 1)
        base case: return 1
        pascal(1, 1)
          pascal(0, 0)
          base case: return 1
          pascal(1, 0)
          base case: return 0
          return sum pascal(0, 0) + pascal(1, 0) = 1 + 0 = 1
        return sum pascal(0, 1) + pascal(1, 1) = 1 + 1 = 2
      pascal(2, 2)
        pascal(1, 1)
          pascal(0, 0)
          base case: return 1
          pascal(1, 0)
          base case: return 0
          return sum pascal(0, 0) + pascal(1, 0) = 1 + 0 = 1
        pascal(2, 1)
        base case: return 0
        return sum pascal(1, 1) + pascal(2, 1) = 1 + 0 = 1
      return sum pascal(1, 2) + pascal(2, 2) = 2 + 1 = 3
    return sum pascal(1, 3) + pascal(2, 3) = 3 + 3 = 6
  pascal(3, 4)
    pascal(2, 3)
      pascal(1, 2)
        pascal(0, 1)
        base case: return 1
        pascal(1, 1)
          pascal(0, 0)
          base case: return 1
          pascal(1, 0)
          base case: return 0
          return sum pascal(0, 0) + pascal(1, 0) = 1 + 0 = 1
        return sum pascal(0, 1) + pascal(1, 1) = 1 + 1 = 2
      pascal(2, 2)
        pascal(1, 1)
          pascal(0, 0)
          base case: return 1
          pascal(1, 0)
          base case: return 0
          return sum pascal(0, 0) + pascal(1, 0) = 1 + 0 = 1
        pascal(2, 1)
        base case: return 0
        return sum pascal(1, 1) + pascal(2, 1) = 1 + 0 = 1
      return sum pascal(1, 2) + pascal(2, 2) = 2 + 1 = 3
    pascal(3, 3)
      pascal(2, 2)
        pascal(1, 1)
          pascal(0, 0)
          base case: return 1
          pascal(1, 0)
          base case: return 0
          return sum pascal(0, 0) + pascal(1, 0) = 1 + 0 = 1
        pascal(2, 1)
        base case: return 0
        return sum pascal(1, 1) + pascal(2, 1) = 1 + 0 = 1
      pascal(3, 2)
      base case: return 0
      return sum pascal(2, 2) + pascal(3, 2) = 1 + 0 = 1
    return sum pascal(2, 3) + pascal(3, 3) = 3 + 1 = 4
  return sum pascal(2, 4) + pascal(3, 4) = 6 + 4 = 10
10

Надеюсь, это поможет.

...