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 ;;

同样的错误。

- unautre

---

我发现你做错的主要问题是试图使用递归函数来解决那个问题... - danii

你应该重新启动caml解释器：它使用了somme2中旧的somme定义，这就是为什么你不需要在第二个定义中使用rec关键字。使用let rec ... = ... and ... = ... ;; 这应该可以工作，除非你应该写成if x= 0 then 0 else somme2 x，因为“return x”很容易让人感到困惑。 - gnomnain

Answer 1

1) 当你的递归永远不停止时，可以在开头添加如下测试：if x == 0 then 0 else ...

2) 在 x-1 周围没有括号，所以 ocaml 读取为 (somme x)-1。请改成 somme (x-1)。

- Gyom

---

尝试了这个： 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 ;;但是结果一样。 - unautre

Answer 2

这里有一个解决方案，也许可以帮助您提高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;;

- 0xFF

Answer 3

循环中没有终止条件。为了修复您的代码：

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) or (1000 mod 3 == 0) 求值为 true，你会得到递归调用 1000 + (somme1 999)，为了完成这个调用，需要递归调用 999 + (somme1 998)。编译器必须保留数字 1000 和 999 在栈上，直到 somme1 执行完毕，但它没有（没有终止条件），所以你的栈填满了，试图存储 1000 + (999 + (996 + (995 + ...。

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

- Aidan Cully

Answer 4

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

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

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

- Francesco

Answer 5

我对OCaml一无所知，但是你的代码似乎没有递归的终止条件。

- anon

---

好的主意。我尝试过这个： let rec somme x = if (( nor (bool_of_int (x mod 3)) (bool_of_int (x mod 5))) & (x > 0)) then x + (somme x-1) else (somme x-1) ;; 但它仍然不能正常工作。 - unautre

如果终止条件为真，则不得调用该函数。 - anon

Answer 6

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

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);;

- Dev M

---

OCaml适合懒惰的打字者，我们认为更少的字符更容易阅读。第4行：...`if mult_3or5 (a-1) then'.. - Str.

Answer 7

我在上述代码中并没有看到任何终止条件。通常，我期望递归在某个特定的x值停止，可能是0或1。你的代码似乎没有包含这样的规定。

请记住，我对OCaml的了解与Neil所承认的一样少。

- Timo Geusch