r - 如何有效地可视化递归函数？

Question

我目前正在编程类(class)中教授递归。我注意到我的学生很难掌握递归的概念。有没有一种很好的方法来可视化该功能对教学目的的作用？

例如，这是一个用于获取第 n 个斐波那契数的 R 函数:

fib_r <- function(n) {
    if(n <= 2) return(1)
    fib_r(n-1) + fib_r(n-2)
}

谢谢。

Answer 1

这就是我将如何解释 R 中的递归函数:
首先，我同意 @AEBilgrau 的观点，即阶乘是递归的一个很好的例子。 (比我认为的斐波那契更好。)
然后我会快速浏览一下为什么阶乘可以定义为递归函数的理论基础，简单的像

4! = 4 * 3 * 2 * 1 = 4 * 3!

然后你可以向他们展示各自的递归 R功能

fact = function(x) if (x == 0) return(1) else return(x * fact(x - 1))
fact(3)
#6

但是 还向他们展示以下输出

#|fact(3) called
#|fact(3) is calculated via 3*fact(2)
#|fact(2) is unknown yet. Therefore calling fact(2) now
#|Waiting for result from fact(2)
#|  fact(2) called
#|  fact(2) is calculated via 2*fact(1)
#|  fact(1) is unknown yet. Therefore calling fact(1) now
#|  Waiting for result from fact(1)
#|  |   fact(1) called
#|  |   fact(1) is calculated via 1*fact(0)
#|  |   fact(0) is unknown yet. Therefore calling fact(0) now
#|  |   Waiting for result from fact(0)
#|  |   |   fact(0) called
#|  |   |   fact(0)=1 per definition. Nothing to calculate.
#|  |   |   fact(0) returning 1 to waiting fact(1)
#|  |   fact(1) received 1 from fact(0)
#|  |   fact(1) can now calculate 1*fact(0)=1*1=1
#|  |   fact(1) returning 1 to waiting fact(2)
#|  fact(2) received 1 from fact(1)
#|  fact(2) can now calculate 2*fact(1)=2*1=2
#|fact(3) received 2 from fact(2)
#|fact(3) can now calculate 3*fact(2)=3*2=6
#[1] 6

源自

# helper function for formatting
tabs = function(n) paste0("|", rep("\t", n), collapse="")

fact = function(x) {
  # determine length of call stack
  sfl = length(sys.frames()) - 1
  # we need to define tmp and tmp1 here because they are used in on.exit
  tmp = NULL
  tmp1 = NULL
  
  # on.exit will print the returned function value when we exit the function ...
  # ... i.e., when one function call is removed from the stack
  on.exit({
    if (sfl > 1) {
      cat(tabs(sfl), "fact(", x, ") returning ",
          tmp, " to waiting fact(", x + 1, ")\n", sep="")
    }
  })
  cat(tabs(sfl), "fact(", x, ") called\n", sep="")
  if (x == 0) {
    cat(tabs(sfl), "fact(0)=1 per definition. Nothing to calculate.\n", sep="")
    # set tmp for printing in on.exit
    tmp = 1
    return(1)
  } else {
    # print some info for students
    cat(tabs(sfl), "fact(", x,
        ") is calculated via ", x, "*fact(", x - 1, ")\n", sep="")
    cat(tabs(sfl),"fact(",x - 1,
        ") is unknown yet. Therefore calling fact(",
        x - 1, ") now\n", sep="")
    cat(tabs(sfl), "Waiting for result from fact(",
        x - 1, ")\n", sep="")
    #call fact again
    tmp1 = fact(x - 1)
    #more info for students
    cat(tabs(sfl), "fact(", x, ") received ", tmp1,
        " from fact(", x - 1, ")\n", sep="")
    tmp = x * tmp1
    cat(tabs(sfl), "fact(", x, ") can now calculate ",
        x, "*fact(", x - 1, ")=", x, "*", tmp1,
        "=", tmp, "\n", sep="")
    return(tmp)
  }
}

fact(3)