Mapping values from the same table recursively

[Anonymous]

I have the following data,

ID	From ID	Type
1	null	a
2	1	b
3	2	c

Desired output,

ID	From ID	Type	Original Type
1	null	a	a
2	1	b	a
3	2	c	a

As you see, I would like a column added, with the Original Type. I want this done recursively, based off the From ID. For example, ID 3 has a From ID which is 2. And ID 2 also has a From ID which is 1. Finally ID 1 does not have a From ID, so I would like the Original Type for ID 3 to be Type from ID 1, which is a.

Heres what I have so far,

let
    Source = #"Copied Table",
    findID = 
        let rowSelected = Table.SelectRows(Table.SelectColumns(Source, {"ID", "Type", "From ID"}), each [ID] = fromID),
        foundID = 
            Table.FirstValue(Table.SelectColumns(rowSelected, {"ID"})),
        foundType = 
            Table.FirstValue(Table.SelectColumns(rowSelected, {"Type"}))
        in finished,

    finished = 
        if foundID = null then foundType else
            let fromID = foundID
            in findID,
        
    tableNew = Table.AddColumn(Source, "Original Type", each if [From ID] = null then [Type] else
            let fromID = [From ID]
            in findID
    )
in tableNew

While I am using Table.SelectRows, this will only ever return 1 row. Since there is only 1 of each ID in my Source. 

My thought here is, I pass the From ID from the original row into the variable "findID" which finds the row with that ID, and checks this row for both the Type and From ID and passes that into another variable "finished" which checks if there is another Found ID in the found row. If there is no Found ID, go ahead and return the Type otherwise change the From ID to the new Found ID and run "findID" again. 

This results in a Cyclic Reference Error!

Any help with this is appreceated. 

Note: this must work with varying lengths of recursion. Some ID's will not have a From ID to begin with, some will recurr 5 or more times before running into a null From ID

[AlexisOlson · Accepted solution]

Try this:

let
    Source = Table.TransformColumnTypes(Table.FromRows(Json.Document(Binary.Decompress(Binary.FromText("i45WMlTSUQKiRKVYnWglIyALJJAE5hkDWSCRZKXYWAA=", BinaryEncoding.Base64), Compression.Deflate)), let _t = ((type nullable text) meta [Serialized.Text = true]) in type table [ID = _t, #"From ID" = _t, Type = _t]),{{"ID", Int64.Type}, {"From ID", Int64.Type}, {"Type", type text}}),
    lookup = (n, tbl) => if tbl{[ID=n]}[From ID] = null then tbl{[ID=n]}[Type] else @lookup(tbl{[ID=n]}[From ID], tbl),
    AddCol = Table.AddColumn(Source, "Original Type", each lookup([ID], Source), type text)
in
    AddCol

The key is the recursive function defined in the query:

lookup = (n, tbl) =>
    if   tbl{[ID=n]}[From ID] = null
    then tbl{[ID=n]}[Type]
    else @lookup(tbl{[ID=n]}[From ID], tbl)

Note that you need to use the @ symbol to reference a function from within the definition of that function.

See also:
https://radacad.com/fibonacci-sequence-understanding-the-power-query-recursive-function