递归最大公约数和递归帕斯卡三角形之间的区别

Question

谁能解释一下这两个递归函数有何不同？我理解每个人的数学方法，但我不明白为什么 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)

  }

Answer 1

这是您的 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

希望有所帮助。

递归最大公约数和递归帕斯卡三角形之间的区别

Difference between recursive greatest common devisor and recursive pascal triangle

recursion

scala

greatest-common-divisor