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

Question

У меня есть небольшая проблема: я хочу, чтобы решить this problem с 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) ваш recusion никогда не останавливается добавить тест, как if x == 0 then 0 else ... в начале

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

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

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