OCaml带记忆化的递归斐波那契函数：返回字符串类型报错解决

你的代码存在两个核心问题：

1. 缓存cache存储的是整数类型，但函数f声明返回字符串类型，类型不匹配直接导致第6行报错；
2. 字符串无法用+运算符做算术加法，OCaml的+仅支持整数运算，字符串拼接用^但这里需要的是数值相加，不能直接用该运算符。

推荐方案：缓存整数，最终转字符串返回 #

这种方式避免了字符串与整数的频繁转换，性能更优。通过内部递归函数处理整数类型的斐波那契计算，主函数负责将结果转为字符串返回：

let cache = Hashtbl.create 100;;
Hashtbl.add cache 0 0;;
Hashtbl.add cache 1 1;;

let f(n:int): string =
    (* 内部递归函数处理整数计算，利用缓存实现记忆化 *)
    let rec fib_int n =
        match Hashtbl.mem cache n with
        | true -> Hashtbl.find cache n
        | false ->
            let result = fib_int (n - 1) + fib_int (n - 2) in
            Hashtbl.add cache n result;
            result
    in
    (* 将整数结果转为字符串返回 *)
    string_of_int (fib_int n)
;;

备选方案：缓存字符串（不推荐） #

如果一定要缓存存储字符串，需要在计算时将字符串转回整数完成算术运算，再转成字符串存入缓存：

let cache = Hashtbl.create 100;;
Hashtbl.add cache 0 "0";;
Hashtbl.add cache 1 "1";;

let rec f(n:int): string =
    match Hashtbl.mem cache n with
    | true -> Hashtbl.find cache n
    | false ->
        (* 将递归返回的字符串转成整数执行加法运算 *)
        let prev1 = int_of_string (f (n - 1)) in
        let prev2 = int_of_string (f (n - 2)) in
        let result = string_of_int (prev1 + prev2) in
        Hashtbl.add cache n result;
        result
;;

关键说明 #

• 优先选择第一种方案，字符串与整数的转换会带来额外性能开销，缓存整数能最大化记忆化的效率；
• OCaml是强类型语言，必须保证函数返回值类型与表达式类型完全一致，原代码的类型不匹配是报错的直接原因。

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