Go Program to Calculate Factorial Using Recursion

A Go program to find factorial using recursion defines a function like func factorial(n int) int that calls itself with n-1 until it reaches 1, returning the product of all numbers from 1 to n.

Examples

Input0

OutputFactorial of 0 is 1

Input5

OutputFactorial of 5 is 120

Input10

OutputFactorial of 10 is 3628800

How to Think About It

To find the factorial of a number using recursion, think of the problem as multiplying the number by the factorial of the number just before it. Keep doing this until you reach 1, which is the base case where you stop the recursion.

Algorithm

1

Get the input number n

2

If n is 0 or 1, return 1 as factorial

3

Otherwise, return n multiplied by factorial of n-1

Code

go

package main

import "fmt"

func factorial(n int) int {
    if n <= 1 {
        return 1
    }
    return n * factorial(n-1)
}

func main() {
    num := 5
    fmt.Printf("Factorial of %d is %d\n", num, factorial(num))
}

Output

Factorial of 5 is 120

Dry Run

Let's trace factorial(5) through the code

1

Call factorial(5)

Since 5 > 1, return 5 * factorial(4)

2

Call factorial(4)

Since 4 > 1, return 4 * factorial(3)

3

Call factorial(3)

Since 3 > 1, return 3 * factorial(2)

4

Call factorial(2)

Since 2 > 1, return 2 * factorial(1)

5

Call factorial(1)

Since 1 <= 1, return 1

6

Calculate results back up

factorial(2) = 2 * 1 = 2 factorial(3) = 3 * 2 = 6 factorial(4) = 4 * 6 = 24 factorial(5) = 5 * 24 = 120

Call	Return Value
factorial(1)	1
factorial(2)	2
factorial(3)	6
factorial(4)	24
factorial(5)	120

Why This Works

Step 1: Base Case

The function stops calling itself when n is 1 or less, returning 1 to avoid infinite recursion.

Step 2: Recursive Call

For values greater than 1, the function calls itself with n-1, breaking the problem into smaller parts.

Step 3: Multiplying Results

Each call multiplies n by the factorial of n-1, building the final factorial value as calls return.

Alternative Approaches

Iterative approach

go

package main

import "fmt"

func factorialIterative(n int) int {
    result := 1
    for i := 2; i <= n; i++ {
        result *= i
    }
    return result
}

func main() {
    num := 5
    fmt.Printf("Factorial of %d is %d\n", num, factorialIterative(num))
}

This uses a loop instead of recursion, which can be more efficient and avoids stack overflow for large numbers.

Using memoization

go

package main

import "fmt"

var memo = map[int]int{0:1, 1:1}

func factorialMemo(n int) int {
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = n * factorialMemo(n-1)
    return memo[n]
}

func main() {
    num := 5
    fmt.Printf("Factorial of %d is %d\n", num, factorialMemo(num))
}

This stores results to avoid repeated calculations, useful if factorial is called many times with overlapping inputs.

Complexity: O(n) time, O(n) space

Time Complexity

The function calls itself n times, so the time grows linearly with the input number.

Space Complexity

Each recursive call adds a layer to the call stack, so space used is proportional to n.

Which Approach is Fastest?

The iterative approach uses constant space and is generally faster, while recursion is simpler but uses more memory.

Approach	Time	Space	Best For
Recursive	O(n)	O(n)	Simple code, small inputs
Iterative	O(n)	O(1)	Large inputs, performance
Memoization	O(n)	O(n)	Repeated calls with same inputs