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

How do I get the output of this function in 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)

The in-order traversal/reordering output from cat() is fine but the output in tnodes is not. I would like to avoid using <<- operator.

CodePudding user response：

The function needs to [at least sometimes] return something interesting, and collect results as recursive calls return. Trying to keep the current logic the same, you want the roots from the first set of recursive calls, the current root, and the roots from the second set of recursive calls. Adding in some message() calls so we can see what's happening:

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))
    }
}

which runs like so:

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

I still don't quite understand the logic here, though; there's quite likely a simpler way to do this.