Go big.Int factorial with recursion

go

Solution

In your `int` version, every `int` is distinct. But in your `big.Int` version, you're actually sharing `big.Int` values. So when you say

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

The expression `n.Sub(n, c)` actually stores `0` back into `n`, so when `n.Mul(n, ...)` is evaluated, you're basically doing `0 * 1` and you get back `0` as a result.

Remember, the results of `big.Int` operations don't just return their value, they also store them into the receiver. This is why you see repetition in expressions like `n.Mul(n, c)`, e.g. why it takes `n` again as the first parameter. Because you could also say`result.Mul(n, c)` and you'd get the same value back, but it would be stored in `result` instead of `n`.

Here is your code rewritten to avoid this problem:

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
}

And here is a slightly more cleaned-up/optimized version (I tried to remove extraneous allocations of `big.Int`s): http://play.golang.org/p/feacvk4P4O

Problem

I am trying to implement this bit of code: ``` func factorial(x int) (result int) { if x == 0 { result = 1; } else { result = x * factorial(x - 1); } return; } ``` as a big.Int so as to make it effective for larger values of x. The following is returning a value of 0 for fmt.Println(factorial(r)) The factorial of 7 should be 5040? Any ideas on what I am doing wrong? ``` 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 } ``` This code on go playground: http://play.golang.org/p/yNlioSdxi4

Original source