Как я могу выразить факториал п! с функцией F #, рекурсивной или другой?

Question

Факториал натурального числа (любое число, большее или равное 0) - это число, умноженное на сам факториал минус один, где факториал 0 определяется как 1.

Например:

0! = 1
1! = 1 * 0!
2! = 2 * 1!
3! = 3 * 2!
4! = 4 * 3!
5! = 5 * 4!

Другой способ написать это - умножить все натуральные числа между 1 и n для n!:

5! = 1 * 2 * 3 * 4 * 5

Каквыразить это с помощью рекурсивной функции в F #?И должен сделать это с помощью рекурсивной функции?

//Factorials!
let factorial n = 
    result = ?

Answer 1

Как, вариант 1:

let rec factorial n =
    match n with
    | 0 | 1 -> 1
    | _ -> n * factorial(n-1)

Как, вариант 2 (хвостовая рекурсия, скомпилированная в цикл):

let factorial n =
    let rec loop i acc =
        match i with
        | 0 | 1 -> acc
        | _ -> loop (i-1) (acc * i)
    loop n 1

Если: нет, см. Мой ответ:

Хотя или хвостовой рекурсии в F #, что использовать, когда?

, где я выступаю за то, чтобы часто избегать итерации и рекурсии в пользу функций более высокого порядка. Но если вы только начинаете, возможно, пока не слишком беспокоитесь об этом совете. (Но тогда посмотрите, например, ответ @ ChaosPandion или, например,

let factorial n = [1..n] |> List.fold (*) 1

---

Или даже:

let factorial n = [1..n] |> List.reduce (*) // doesn't require the 2nd parameter

Answer 2

Вот еще один пример:

let factorial (num:int) =
    seq { for n in [1..num] -> n }
    |> Seq.reduce (fun acc n -> acc * n)

Этот пример может быть немного понятнее:

let factorial num =
    [1..num] |> Seq.fold (fun acc n -> acc * n) 1

Answer 3

Ответы Брайана наиболее практичны, но вот решение в стиле прохождения продолжения:

let rec factorial n = 
  let rec loopk i k = 
    match i with
    | 0 | 1 -> k i
    | _ -> loopk (i-1) (fun r -> k (i * r))
  in loopk n (fun r -> r)

Answer 4

Мое любимое решение F # для рекурсивных последовательностей - это ... бесконечные хвостовые рекурсивные последовательности!:

let factSeq =    
    let rec factSeq m n = 
        seq { let m = m * n
              yield m
              yield! factSeq m (n+1I) }
    seq { yield 1I ; yield 2I ; yield! (factSeq 2I 3I) }

let factTake n = factSeq |> Seq.take n //the first n terms
let fact n = factSeq |> Seq.nth (n-1) //the nth term

Я использую здесь BigIntegers, поскольку факториальная последовательность растет очень быстро (продолжайте, попробуйте 20 000-й член).

Я в целом согласен с рекомендацией Брайана использовать функции более высокого порядка над итерационными циклами или рекурсивными циклами (хвостовая рекурсия + аккумулятор), когда это возможно. Но я думаю, что в этом случае бесконечная последовательность, как я показал, является более гибкой, поскольку она генерирует все члены факториальной последовательности вплоть до требуемого (factTake), и каждый член требует только одного шага умножения (n * (п-1)). Принимая во внимание, что если бы вы хотели, чтобы первые n членов использовали сложное решение, каждое вычисление было бы выполнено независимо и не принесло бы пользы от предыдущего вычисления.

Answer 5

Как бы я объявил рекурсивную функцию для этого?

Прежде всего, чтобы определить рекурсивную функцию, вы должны использовать let rec вместо let (поскольку let не позволяет ссылаться на рекурсивную функцию, которую вы определяете).

Для рекурсивного определения факториальной функции самым простым (но не самым эффективным) способом было бы использование стандартного математического определения факториальной функции.

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

Answer 6

Вот более простая реализация

let rec bfact (n):bigint = 
    match n with
        | i when i<0 -> bigint.Zero
        | 0 | 1 -> bigint(1)
        | _ -> ( bfact(n-1) * bigint(n) )

И для проверки

bfact(50)

val bfact : n:int -> bigint
val it : bigint =
  30414093201713378043612608166064768844377641568960512000000000000