Find all possible paths in a recursive way

Question

Sorry because this question may sound very noob for a lot of people but I am absolutely bad at recursion and need some help.

Here is the model:

struct Chain {
    let initialId: Int
    let chains: [SubChain]
}

struct SubChain {
    let id: Int
    let subChains: [SubChain]
    
    init(_ id: Int, subChains: [SubChain] = []) {
        self.id = id
        self.subChains = subChains
    }
}

An example:

let chain = Chain(
    initialId: 1,
    chain: [
        SubChain(
            2,
            subChains: [
                SubChain(3),
                SubChain(4)
            ]
        ),
        SubChain(
            5,
            subChains: [
                SubChain(6),
                SubChain(
                    7,
                    subChains: [
                        SubChain(8)
                    ]
                )
            ]
        ),
        
    ]
)

Now I would like to find all the possible paths, which would be:

1 -> 2 -> 3

1 -> 2 -> 4

1 -> 5 -> 6

1 -> 5 -> 7 -> 8

I started writing this in Chain but I have no idea how to to this recursively.

var straightChain: [[Int]] {
    var result: [[Int]] = []
    for subChain in chain {
        for c in subChain.subChains {
            var subResult: [Int] = [initialId, subChain.id]



            result.append(subResult)
        }
    }
    return result
}

Can you please help me? Thank you for your help

Answer 1

Here is the answer for your question

Below is the recursion for subchain

func findAllPossibleSubChain(_ chain: SubChain) -> [[Int]] {
    if chain.subChains.count == 0 {
        return [[chain.id]]
    }

    var result : [[Int]] = []

    for sub in chain.subChains {
        let temp = findAllPossibleSubChain(sub)
        for val in temp {
            // Recursion for the subChain if have array
            result.append([chain.id] + val)
        }
    }

    return result
}

Main

var result : [[Int]] = []
// Because of chain only have 1
if chain.chains.count == 0 {
        result = [[chain.initialId]]
} else {
        for sub in chain.chains {
             let temp = findAllPossibleSubChain(sub)
             for val in temp {
                result.append([chain.initialId] + val)
             }
        }
}

print("result: ", result) // result:  [[1, 2, 3], [1, 2, 4], [1, 5, 6], [1, 5, 7, 8]]