Рекурсивные функции в OCaml

1) ваш отказ никогда не прекращается, добавьте тест, например if x == 0 then 0 else ... в начале

2) вы не заключаете скобки вокруг x-1, поэтому ocaml читает (somme x)-1. Вместо этого напишите somme (x-1).

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

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

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

Вот простое решение проблемы, возможно, оно поможет вам улучшить свои навыки 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;;

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

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

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

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

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

попробуйте использовать сопоставление с образцом и синтаксис параметров фильтрации:

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