在Kotlin中计算给定数的阶乘

1. Introduction

Factorial is a mathematical operation that calculates the product of all positive integers from 1 to a given number. It is denoted by n! and is defined as n! = n * (n-1) * (n-2) * … * 2 * 1.

In this tutorial, we’ll explore how to find the factorial of a given number in Kotlin using both recursive and iterative methods.

2. Find a Factorial Using Recursion

Recursive functions are functions that call themselves to solve a problem. Calculating the factorial of a number using recursion is straightforward in Kotlin. To understand this approach better, let’s explore the mathematical basis of recursion for factorials:

The factorial of a positive integer n, denoted as n!, is defined as the product of all positive integers from 1 to n. Mathematically, we can expand it as follows:

n! = n * (n-1)!

This equation tells us that the factorial of n can be calculated by multiplying n with the factorial of (n-1). We can start to see the recursive definition in this pattern.

Now, let’s translate this mathematical insight into Kotlin code:

fun factorialRecursive(n: Int): Int {
    require(n >= 0) { "n must be positive" }
    return if (n <= 1) {
        1
    } else {
        n * factorialRecursive(n - 1)
    }
}

In this code block, we define a recursive function, factorialRecursive(), that calculates the factorial of a given number n. It checks if n is less than or equal to 1, in which case it returns 1 (base case). Otherwise, it recursively multiplies n with the factorial of n-1, effectively applying the recursive formula.

This recursive approach elegantly captures the essence of factorial computation and demonstrates how recursion can be a powerful tool for solving problems with clear mathematical recursive definitions. Let’s validate that our function works with a unit test:

@Test
fun `Should calculate a factorial recursively`() {
    val result = factorialRecursive(7)
    assertEquals(7 * 6 * 5 * 4 * 3 * 2 * 1, result, "7! should be exactly 5040")
}

2.1. Tailrec Recursion

Kotlin supports tail-recursive functions, which are optimized by the compiler to prevent stack overflow errors for large inputs. The primary rule for a tailrec function is that the recursive call must be the last call in the function. To use tail recursion for calculating a factorial, we can use the tailrec modifier:

tailrec fun factorialTailRecursive(n: Int, accumulator: Int = 1): Int {
    return if (n <= 1) {
        accumulator
    } else {
        factorialTailRecursive(n - 1, n * accumulator)
    }
}

This code block introduces a tail-recursive version of the factorial function. The tailrec keyword indicates that this function is tail-recursive, allowing the Kotlin compiler to optimize it for efficient execution, converting it to a simple loop. It uses an accumulator to keep track of the intermediate results. Let’s also create a small unit test to validate that it calculates the correct result:

@Test
fun `Should calculate a factorial tail-recursively`() {
    val result = factorialTailRecursive(6)
    assertEquals(6 * 5 * 4 * 3 * 2 * 1, result, "6! should be exactly 720")
}

3. Find a Factorial Using a Loop

An alternative to recursion is using a loop, which can be more memory-efficient for large inputs:

fun factorialIterative(n: Int): Int {
    var result = 1
    for (i in 1..n) {
        result *= i
    }
    return result
}

This code block presents an iterative approach to calculating the factorial. It defines a function factorialIterative() that uses a loop to multiply the numbers from 1 to n together, updating the result variable at each step. Finally, let’s create a unit test to validate that our code is correct:

@Test
fun `Should calculate a factorial iteratively`() {
    val result = factorialIterative(5)
    assertEquals(5 * 4 * 3 * 2 * 1, result, "5! should be exactly 120")
}

4. Conclusion

In this article, we’ve explored two methods for finding the factorial of a given number in Kotlin: recursively and iteratively The recursive approach provides a concise and elegant solution, while the iterative approach is more efficient in terms of memory usage, especially for large inputs. We’ve also seen how we can get many of the same benefits from the iterative approach while using the special tail recursion feature of Kotlin.

As always, the code used in this article is available over on GitHub.