F# 如何通过递归实现向列表末尾追加元素

你当前的代码仅实现了空列表场景的处理，缺失非空列表的递归匹配分支，补充后即可完成完整功能。

完整实现代码 #

let rec add lst value =
    match lst with
    | [] -> [value]
    | head :: tail -> head :: add tail value

实现逻辑说明 #

• F#中的默认列表是单向不可变链表，结构为「头元素 + 剩余尾列表」，无法直接修改尾节点，必须递归遍历到列表末端后，逐层回拼节点才能完成追加
• 你原有代码中的[] -> [value]是递归终止条件：当遍历到列表最末端的空节点时，返回包裹了待追加值的单元素列表，作为整个拼接流程的终点
• 新增的head :: tail -> head :: add tail value是非空列表的处理分支：将当前列表拆分为头元素和剩余尾列表，保留当前头元素，对尾列表递归执行追加操作，最后把当前头元素和处理完成的尾列表用 cons 运算符::拼接起来

执行流程示例 #

以调用add [1; 2; 3] 4为例，递归展开和回拼的过程如下：

add [1;2;3] 4
→ 1 :: add [2;3] 4
→ 1 :: 2 :: add [3] 4
→ 1 :: 2 :: 3 :: add [] 4
→ 1 :: 2 :: 3 :: [4]
→ [1;2;3;4]

注意：受不可变单向链表的结构限制，该尾追加实现的时间复杂度为O(n)，需要遍历整个列表才能完成操作。如果需要高频执行尾追加，建议选用ResizeArray（即.NET中的List）这类支持O(1)尾追加的可变数据结构；如果是递归语法练习，上述写法是符合函数式编程范式的标准实现。

内容的提问来源于stack exchange，提问作者kelperg1