Нужна помощь в последовательности F #

Question

Я новичок в F # (начал изучать только сегодня), я пытался рекурсивно реализовать последовательность Фибоначчи.Я не уверен, неправильно ли это синтаксически или логически

let rec fibonacciRecursive (x : int) = seq{
        match x with
        | 0     -> yield! [0]
        | 1     -> yield! [0; 1]
        | _     -> yield! fibonacciRecursive 
                   |> Seq.pairwise 
                   |> Seq.map (fun (prev, next) -> prev + next)
                   |> Seq.toList
        }

Answer 1

Рецепт для рекурсивного создания последовательности состоит в создании функции, которая создает последовательность из некоторого «состояния» (здесь continueFrom состояние - a и b).Функция должна выдавать элемент, а затем выдавать себя с состоянием, соответствующим последовательности следующего элемента.

 let fibonacciSequence =
     let rec continueFrom a b =
         seq {
             yield a
             yield! continueFrom b (a + b)
         }
     continueFrom 0 1

Обратите внимание, что fibonacciSequence - это бесконечная последовательность, что означает, что вы не можете преобразовать его в список напрямую.Если вы хотите сначала n предметов, вы можете использовать Seq.take n fibonacciSequence.

Answer 2

То, как вы пытаетесь создать последовательность Фибоначчи, будет работать лучше, если использовать удобную функцию Seq.unfold, которая была разработана для такого рода ситуаций.Вы передаете ему функцию и начальное состояние, и она повторно вызывает эту функцию, чтобы вычислить следующее значение последовательности на основе текущего состояния.Его параметры приведены в порядке Seq.unfold function initialState, но я обычно предпочитаю записывать его как initialState |> Seq.unfold function.Функция возвращает либо None для остановки последовательности, либо Some (nextValue, nextState) для продолжения последовательности (которая может создавать бесконечные последовательности).

В случае последовательности Фибоначчи ее создание с Seq.unfold будет выглядетькак это:

let fibUnfold = (0,1) |> Seq.unfold (fun (a, b) -> Some(b+a, (b, b+a)))
let fib = seq { yield 0; yield 1; yield! fibUnfold }

for i in fib |> Seq.take 10 do  // Infinite sequence, so take a finite number
    printf "%d, "
printfn ""
// Prints "0, 1, 1, 2, 3, 5, 8, 13, 21, 34, "

Answer 3

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

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

Вот как я бы это сделал:

Всякий раз, когда у вас есть некоторая рекурсивная функция, которая не является хвостовой рекурсивной (она заканчивается на f x (recCall y)вы создаете себе рекурсивную подфункцию, которая выглядит как let rec subF x y, т.е. вы перемещаете хвостовую часть вашего исходного кода в вашу вспомогательную подфункцию subf).С Фибоначчи, вот как это будет выглядеть в моем случае:

let fib n =
    let rec worker state x =
        if x = 0 then state 
        else
            match state with
            | [] -> worker [0] (x-1)
            | [0] -> worker [1;0] (x-1)
            | (a::b::_) -> worker ((a+b)::state) (x-1)
    worker [] n

И - как легко видеть, рекурсивный вызов подфункции worker - это хвостовая рекурсия(он ничего не делает после рекурсивного вызова).

Answer 4

Как указал Федор, в третьем случае match есть синтаксическая ошибка, потому что вы на самом деле не передаете параметр в функцию fibonacciRecursive.Однако, если вы исправите это, передав x, вы обнаружите, что ваша функция выдает StackOverflowException при выполнении.Это потому, что вы рекурсивно пытаетесь сгенерировать всю последовательность для каждого значения.

Очень простое решение для Фибоначчи в F # выглядит следующим образом:

let rec fib = function
| 0 -> 0
| 1 -> 1
| n -> fib (n - 1) + fib (n - 2)

Однако, это также в конечном итоге приведет к переполнению стека, поскольку вызовы не являются "хвостовыми рекурсивными", то естьрекурсия - это не последнее, что происходит в функции (в этом случае добавление - последнее, что должно происходить).Вы можете сделать хвостово-рекурсивное решение, отложив выполнение каждого элемента с продолжением, так что рекурсивный вызов находится в хвостовой позиции:

let fib n =
    let rec fib cont = function
    | n when n < 2 -> cont n
    | n -> (n - 1) |> fib (fun x -> (n - 2) |> fib (fun y -> cont (x + y))) 
    fib id n

Это немного сложно следовать, и это часто требуетнекоторое время, чтобы привыкнуть думать о написании функций таким образом.Вот версия, использующая двойные обратные галочки, чтобы разрешить описательным именам параметров продолжения, если это помогает понять, что происходит:

let fib n =
    let rec fib cont = function
    | n when n < 2 -> 
        cont n
    | n -> 
        (n - 1) |> fib (fun ``fib (n-1)`` -> 
            (n - 2) |> fib (fun ``fib (n-2)`` -> 
                cont (``fib (n-1)`` + ``fib (n-2)``))) 
    fib id n