CODEWITHSUNDEEP
recursionf#tail-recursion
user2431438
user2431438

Reputation: 307

F# tail recursion on tree's path listing

I'm trying to implement a recursive function that takes in a tree and list all the path it has.

My current implementation doesn't work:

let rec pathToList tree acc =
    match tree with
    | Leaf -> acc
    | Node(leftTree, x, rightTree) ->
        let newPath = x::acc
        pathToList leftTree newPath :: (pathToList rightTree newPath)

...because pathToList leftTree newPath doesn't return an element but a list, hence error.

This could be fixed with set, like:

let rec pathToList2 t acc =
    match t with
    | Leaf -> Set.singleton acc
    | Node(leftTree, x, rightTree) ->
        let newPath = x::acc
        Set.union (pathToList2 leftTree newPath) (pathToList2 rightTree newPath)

Now, I'm a bit stuck on solving this using the list (former) rather then set (later), any suggestion on how would I solve that using tail recursion?

Upvotes: 3

Views: 447

Answers (1)

Tarmil
Tarmil

Reputation: 11362

In order to solve this without resorting to @ (which is inefficient because it is linear in the length of the first list), you will need two accumulators: one for the path down to the parent node (so you can build the path to the current node), and one for all the paths you've found so far (so you can add the paths you find).

let rec pathToListRec tree pathToParent pathsFound =
    match tree with
    | Leaf -> pathsFound
    | Node (left, x, right) ->
        let pathToHere = x :: pathToParent

        // Add the paths to nodes in the right subtree
        let pathsFound' = pathToListRec right pathToHere pathsFound

        // Add the path to the current node
        let pathsFound'' = pathToHere :: pathsFound'

        // Add the paths to nodes in the left subtree, and return
        pathToListRec left pathToHere pathsFound''

let pathToList1 tree = pathToListRec tree [] []

As far as tail-recursion goes, you can see that one of the two recursive calls in the above function is in tail position. However, there is still a call in non-tail position.

Here's a rule of thumb for tree processing functions: you can't easily make them fully tail-recursive. The reason is simple: if you do it naively, at least one of the two recursions (down to the left subtree or to the right subtree) will necessarily be in non-tail position. The only way to do it is to simulate the call stack with a list. This means that you will have the same runtime complexity as a non-tail-recursive version, except you're using a list instead of the system-provided call stack, so it's probably going to be slower.

Here is anyway what it looks like:

let rec pathToListRec stack acc =
    match stack with
    | [] -> acc
    | (pathToParent, tree) :: restStack ->
        match tree with
        | Leaf -> pathToListRec restStack acc
        | Node (left, x, right) ->
            let pathToHere = x :: pathToParent

            // Push both subtrees to the stack
            let newStack = (pathToHere, left) :: (pathToHere, right) :: restStack

            // Add the current path to the result, and keep processing the stack
            pathToListRec newStack (pathToHere :: acc)

// The initial stack just contains the initial tree
let pathToList2 tree = pathToListRec [[], tree] []

The code doesn't look too bad, but it takes more than twice as long as the non-tail-recursive one and does a lot more allocations, because we're using a list to do the job of the stack!

> #time;;
--> Timing now on
> for i = 0 to 100000000 do ignore (pathToList1 t);;
Real: 00:00:09.002, CPU: 00:00:09.016, GC gen0: 3815, gen1: 1, gen2: 0
val it : unit = ()
> for i = 0 to 100000000 do ignore (pathToList2 t);;
Real: 00:00:21.882, CPU: 00:00:21.871, GC gen0: 12208, gen1: 3, gen2: 1
val it : unit = ()

In conclusion: The rule "Make it tail-recursive it will be faster!" shouldn't be followed to the extreme when several recursive calls need to be made, because it requires the code to be changed in a way that will make it even slower.

Upvotes: 3

Related Questions