去大.用递归的因子

Question

我正在尝试实现这段代码:

func factorial(x int) (result int) {
  if x == 0 {
    result = 1;
  } else {
    result = x * factorial(x - 1);
  }
  return;
}

作为一个big.Int,以使其对更大的x值有效.

以下为fmt.Println(factorial(r))返回值0

阶乘7应该是5040？

关于我做错了什么的任何想法？

package main

import "fmt"
import "math/big"

func main() {
        fmt.Println("Hello, playground")

    //n := big.NewInt(40)
    r := big.NewInt(7)

    fmt.Println(factorial(r))

}

func factorial(n *big.Int) (result *big.Int) {
    //fmt.Println("n = ", n)
    b := big.NewInt(0)
    c := big.NewInt(1)

    if n.Cmp(b) == -1 {
        result = big.NewInt(1)
    }
    if n.Cmp(b) == 0 {
        result = big.NewInt(1)
    } else {
        // return n * factorial(n - 1);
        fmt.Println("n = ", n)
        result = n.Mul(n, factorial(n.Sub(n, c)))
    }
    return result
}

这个代码在游乐场:http://play.golang.org/p/yNlioSdxi4

Answer 1

去包math.big有func (*Int) MulRange(a, b int64).当第一个参数设置为1时调用,它将返回b!:

package main

import (
    "fmt"
    "math/big"
)

func main() {
    x := new(big.Int)
    x.MulRange(1, 10)
    fmt.Println(x)
}

会生产

3628800

Answer 2

在您的int版本中,每个int都是不同的.但在您的big.Int版本中,您实际上是在共享big.Int价值观.所以当你说

result = n.Mul(n, factorial(n.Sub(n, c)))

表达式n.Sub(n, c)实际上存储0回来n,所以当n.Mul(n, ...)评估时,你基本上都在做0 * 1,结果你回来0了.

请记住,big.Int操作的结果不只是返回它们的值,它们还将它们存储到接收器中.这就是为什么你会在表达式中看到重复n.Mul(n, c),例如为什么它n再次作为第一个参数.因为您也可以说result.Mul(n, c)并且您将获得相同的值,但它将被存储result而不是n.

以下是您重写的代码以避免此问题:

func factorial(n *big.Int) (result *big.Int) {
    //fmt.Println("n = ", n)
    b := big.NewInt(0)
    c := big.NewInt(1)

    if n.Cmp(b) == -1 {
        result = big.NewInt(1)
    }
    if n.Cmp(b) == 0 {
        result = big.NewInt(1)
    } else {
        // return n * factorial(n - 1);
        fmt.Println("n = ", n)
        result = new(big.Int)
        result.Set(n)
        result.Mul(result, factorial(n.Sub(n, c)))
    }
    return
}

这是一个稍微清理/优化的版本(我试图删除big.Ints的无关分配):http://play.golang.org/p/feacvk4P4O