OCaml 中的递归函数

Question

我有一个小问题：我想用 OCaml 解决这个问题 , 所以我尝试了这个->

-> let rec somme x = if ( nor (bool_of_int (x mod 3)) (bool_of_int (x mod 5))) then x + (somme x-1) else (somme x-1) ;;

val somme : int -> int = <fun>

-> somme 1000 ;;

Stack overflow during evaluation (looping recursion?).

我做错了什么？

---

我尝试过的新代码：

let somme2 x = if (( nor (bool_of_int (x mod 3)) (bool_of_int (x mod 5)))) then x + somme (x-1) else somme (x-1) ;;

let somme x = if x = 0 then x else somme2 x ;;

同样的错误。

Answer 1

1) 你的回避永远不会停止，在开头添加一个像 if x == 0 then 0 else ... 这样的测试

2) 你不会在你的 x-1，因此 ocaml 读取 (somme x)-1。请改为编写 somme (x-1)。

Answer 2

正如其他人指出的那样，您应该包括对基本情况的测试。您可以使用模式匹配：

match x with
| 0 -> ...
| n -> ...;;

函数式语言通常与数学符号密切相关，而模式匹配实际上与您在纸上编写方程的方式非常相似。

Answer 3

这是该问题的一个简单解决方案，也许它会帮助您提高 OCaml 技能

(*generates a list of the multiples of num and stops at max*)
let gen_mult num max=

  let rec gen i=

  if i*num>=max then []

  else (i*num)::gen (i+1)

  in gen 1;;

let m3=gen_mult 3 1000;;

let m5=gen_mult 5 1000;;

(*sums the multiples of 3*)
let s3=List.fold_left (fun acc x->x+acc) 0 m3;;

(*sums the multiples of 5 except those of 3*)
let s5=List.fold_left (fun acc x->if x mod 3=0 then acc else x+acc) 0 m5;;

let result=s3+s5;;

Answer 4

循环中没有终止条件。修复代码：

let rec somme1 x = 
  if x <= 0
    then 0
    else if ((x mod 3) = 0) or ((x mod 5) = 0)
      then x + (somme1 (x-1))
      else somme1 (x-1);;

somme1 1000;;

要改进代码，您需要使函数成为尾递归。

let rec somme2 x accum = 
  if x <= 0
    then accum
    else if ((x mod 3) = 0) or ((x mod 5) = 0)
      then somme2 (x-1) (accum+x)
      else somme2 (x-1) accum

somme2 1000 0;;

两个版本的区别在于，在尾递归的情况下，递归调用的结果与函数的结果完全相同，因此不需要存储中间状态来完成递归函数之后的计算。叫。当您调用 somme1 1000;; 时，因为 (1000 mod 5 == 0) 或 (1000 mod 3 == 0) 评估 true ，您将得到递归调用 1000 + (somme1 999)，要完成该调用，需要递归调用 999 + (somme1 998)。编译器必须将数字 1000 和 999 保留在堆栈上，直到 somme1 完成执行，但事实并非如此（无终止条件） ，因此您的堆栈在尝试存储 1000 + (999 + (996 + (995 + ...) 时已满。

这相当于 ((((0 + 1000) + 999) + 996) + 995) + ...，但在这种情况下，不需要中间值来处理递归调用的结果（也就是说，递归调用的返回值与函数本身的返回值），因此不需要额外的堆栈空间，如果第二个版本与第一个版本具有相同的错误，则它不会耗尽堆栈，而是会无限期地继续执行。这被认为是一种改进:-)

Answer 5

我知道关于 OCaml 的 zip，但看起来你的代码没有递归的终止条件。

Answer 6

我在上面的代码中确实没有看到任何终止条件？通常，我希望递归在 x 的某个值（可能是 0 或 1）处停止。您的代码似乎不包含任何这样的规定。

请记住，我对 OCaml 的了解和 Neil 承认的一样多。

Answer 7

尝试使用模式匹配和过滤参数
语法：

let f a= match a with
| a when (a=..)  -> ...
| a when (a=..)-> ...
| _ -> ...;;

let f = function
   p1 -> expr1
 | p2 -> expr2
 | p3 -> ...;;

解决方案：

---

let mult_3or5  a = match a with
  a when ((a mod 3=0)||(a mod 5=0)) ->true
 |_  ->false;;

---

let rec somme_mult_3or5 = function 
    a when (a=0) -> failwith "Indice invalide"    
   |a when (a=1) -> 0
   |a -> if (mult_3or5 (a-1)=true) then ((a-1)+ somme_mult_3or5 (a-1)) 
         else somme_mult_3or5 (a-1);;