R语言：无返回值递归辅助函数无法更新主函数变量的原因

可复现代码 #

# recursive helper function
# a = array representation of the binary tree
# i = position of the root that we are trying to add to inorder_a
# inorder_a = array representation of a up till i
add_node <- function(a, i, inorder_a) {
  print(paste("a:", paste(a, collapse = ' '), 
              "i:", i, 
              'a[i]:', a[i],
              "inorder_a:", paste(inorder_a, collapse = ' '), 
              sep = ' '))
  if(is.na(a[i]) == FALSE) {
    # add the left child of the root node in position i, which is in position 2*i
    add_node(a, 2*i, inorder_a)
    # add the root node in position i of a
    inorder_a <- append(inorder_a, a[i])
    # add the right child of the root node in position i, which is in position (2*i + 1)
    add_node(a, (2*i)+1, inorder_a)
  }
}

# main function that calls add_node() to return the in-order traversal of binary tree array a
get_inorder_traversal_recursion <- function(a) {
  n <- length(a)
  
  # corner cases
  if(n <= 1) return(a)
  
  # initiate output array
  inorder_a <- c()
  
  # add binary tree a, whose head/root is in position 1
  add_node(a, 1, inorder_a)
  
  return(inorder_a)
}

问题描述 #

调用get_inorder_traversal_recursion(c(1, NA, 2, 3))时，print输出显示递归过程中inorder_a确实在更新：

[1] "a: 1 NA 2 3 i: 1 a[i]: 1 inorder_a: "
[1] "a: 1 NA 2 3 i: 2 a[i]: NA inorder_a: "
[1] "a: 1 NA 2 3 i: 3 a[i]: 2 inorder_a: 1"
[1] "a: 1 NA 2 3 i: 6 a[i]: NA inorder_a: 1"
[1] "a: 1 NA 2 3 i: 7 a[i]: NA inorder_a: 1 2"

但函数最终返回值为空（或NA），主函数中的inorder_a从未被实际更新。

原因分析 #

R采用**传值调用（pass-by-value）**的参数传递机制：当你将主函数中的inorder_a传入add_node时，函数内部会创建该变量的独立副本，所有对inorder_a的修改都只作用于这个副本，不会影响主函数中的原始变量。同时你的add_node没有返回修改后的副本，导致主函数中的inorder_a始终保持初始的空向量状态。

解决方案 #

修改add_node函数，让它返回更新后的inorder_a，并在主函数和递归调用中接收这个返回值：

add_node <- function(a, i, inorder_a) {
  print(paste("a:", paste(a, collapse = ' '), 
              "i:", i, 
              'a[i]:', a[i],
              "inorder_a:", paste(inorder_a, collapse = ' '), 
              sep = ' '))
  if(!is.na(a[i])) {
    # 递归左子树，接收更新后的inorder_a
    inorder_a <- add_node(a, 2*i, inorder_a)
    # 添加当前节点
    inorder_a <- append(inorder_a, a[i])
    # 递归右子树，接收更新后的inorder_a
    inorder_a <- add_node(a, (2*i)+1, inorder_a)
  }
  # 返回修改后的inorder_a
  return(inorder_a)
}

get_inorder_traversal_recursion <- function(a) {
  n <- length(a)
  
  if(n <= 1) return(a)
  
  inorder_a <- c()
  
  # 接收辅助函数返回的结果
  inorder_a <- add_node(a, 1, inorder_a)
  
  return(inorder_a)
}

现在调用get_inorder_traversal_recursion(c(1, NA, 2, 3))会返回正确的中序遍历结果[1] 1 2，和print输出中的最终inorder_a一致。

内容的提问来源于stack exchange，提问作者Amazonian