如何从（双重）递归函数输出？

Question

如何在 R 中获取此函数的输出？

nodes2 <- c(1,2,4,5,10,11,20,21)
getLeftOrder <- function(root, snodes, nodes) {
  if ( length(nodes) == 0 ) {
    return(snodes)
  } else {
    nodes <- nodes[-(which(nodes == (2*root)))]
    getLeftOrder(2*root, snodes, nodes)
    snodes <- c(snodes, root)
    cat(root, fill = TRUE)
    nodes <- nodes[-(which(nodes == (2*root+1)))]
    getLeftOrder(2*root+1, snodes, nodes)
  }
}
tnodes <- getLeftOrder(1, vector('integer'), nodes2)

cat() 的有序 traversal/reordering 输出是好的，但 tnodes 的输出不是。我想避免使用 <<- 运算符。

Answer 1

该函数需要[至少有时] return 一些有趣的东西，并将结果收集为递归调用 return。试图保持当前逻辑相同，您需要来自第一组递归调用的根、当前根和来自第二组递归调用的根。添加一些 message() 调用以便我们可以看到发生了什么：

nodes2 <- c(1,2,4,5,10,11,20,21)

getLeftOrder <- function(root, nodes) {
    message('root: ', root, '  nodes: ', paste(nodes, collapse = ' '))
    if ( length(nodes) == 0 ) {
        return(NULL)
    } else {
        nodes <- nodes[-which(nodes == 2*root)]
        r1 <- getLeftOrder(2*root, nodes)
        message(root)
        nodes <- nodes[-which(nodes == 2*root + 1)]
        r2 <- getLeftOrder(2*root+1, nodes)
        return(c(r1, root, r2))
    }
}

运行方式如下：

tnodes <- getLeftOrder(1, nodes2)
#> root: 1  nodes: 1 2 4 5 10 11 20 21
#> root: 2  nodes: 1 4 5 10 11 20 21
#> root: 4  nodes: 1 5 10 11 20 21
#> root: 8  nodes:
#> 4
#> root: 9  nodes:
#> 2
#> root: 5  nodes: 1 10 11 20 21
#> root: 10  nodes: 1 11 20 21
#> root: 20  nodes: 1 11 21
#> root: 40  nodes:
#> 20
#> root: 41  nodes:
#> 10
#> root: 21  nodes: 1 11
#> root: 42  nodes:
#> 21
#> root: 43  nodes:
#> 5
#> root: 11  nodes: 1 20 21
#> root: 22  nodes:
#> 11
#> root: 23  nodes:
#> 1
#> root: 3  nodes:

tnodes
#> [1]  4  2 20 10 21  5 11  1

虽然我还是不太明白这里的逻辑；很可能有更简单的方法来做到这一点。

如何从（双重）递归函数输出？

How do I output from a (doubly) recursive function?

r

recursion