Рекурсивные функции в 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

Нет завершающего условия в цикле. Чтобы исправить свой код:

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) + ..., но в этом случае нет никаких промежуточных значений, необходимых для работы с результатом рекурсивных вызовов (т. Е. Возвращаемое значение рекурсивного вызова совпадает с возвращаемым значением самой функции), поэтому дополнительное пространство в стеке не требуется. Вторая версия работает таким образом. Если бы у него была та же ошибка, что и у первого, он бы не исчерпал стек, а просто продолжал бы работать бесконечно. Это считается улучшением. : -)

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

Как уже отмечали другие, вы должны включить тест для базового случая. Вы можете использовать сопоставление с образцом:

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

Функциональные языки часто зеркально отражают математические обозначения, и сопоставление с образцом на самом деле очень похоже на то, как вы пишете уравнения на бумаге.

Answer 5

Я знаю zip об OCaml, но похоже, что у вашего кода нет условия завершения для рекурсии.

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

Answer 7

Я действительно не вижу никаких условий завершения в коде выше? Как правило, я ожидаю, что рекурсия остановится для определенного значения x, возможно, 0 или 1. Ваш код, кажется, не содержит каких-либо положений, подобных этому.

Пожалуйста, имейте в виду, что я знаю об OCaml столько, сколько признает Нил.