Как найти факториал в питоне через while

Вступление

По определению, факториал – это произведение положительного целого числа и всех положительных целых чисел, которые меньше или равны данному числу. Другими словами, получение факториала числа означает умножение всех целых чисел от этого числа вплоть до 1.

По правилу 0! = 1

Факториал – это целое число, за которым следует восклицательный знак.

5! обозначает факториал из пяти.

Чтобы вычислить факториал, мы умножаем число на каждое целое число, меньшее его, пока не дойдём до 1:

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

Запомните эти простые правила, ведь в этом уроке мы узнаем, как вычислять факториал целого числа с помощью Python, используя циклы и рекурсию. Начнём с вычисления факториала с помощью циклов.

Вычисляем факториал с помощью циклов

Мы можем вычислять факториалы, используя как цикл while, так и цикл for. Общий процесс довольно похож в обоих случаях. Всё, что нам нужно, – это параметр в качестве входных данных и счетчик.

Давайте начнем с цикла for:

def get_factorial_for_loop(n):
    result = 1
    if n > 1:
        for i in range(1, n+1):
            result = result * i
        return result
    else:
        return 'n has to be positive'

Возможно, вы заметили, что мы считаем, начиная с 1 до n-числа, в то время как в определении мы описали факториал, как произведение положительного целого числа и всех положительных целых чисел до 1. Но по законам математики:

Проще говоря, (n – (n-1)) всегда равно 1.

Это значит, что не важно, в каком направлении мы считаем. Можем начать с 1 и увеличиваться в направлении n-числа, или он может начинаться с n-числа и уменьшаться в направлении 1. Теперь, когда мы всё объяснили, начнём разбирать функцию, о которой говорили.

Наша функция принимает параметр n, который обозначает число, для которого мы вычисляем факториал. Сначала мы определяем переменную с именем result и присваиваем ей значение 1.

Вы можете спросить, почему 1, а не 0?

Потому что если бы мы присвоили ему 0, то все последующие умножения на 0, естественно, привели бы к 0.

Затем мы начинаем наш цикл for в диапазоне от 1 до n+1. Помните, что диапазон Python остановится перед вторым аргументом. Чтобы включить и последнее число, мы просто добавляем еще 1.

Внутри цикла for мы умножаем текущее значение result на текущее значение вашего индекса i.

Наконец, мы возвращаем конечное значение result. Давайте протестируем нашу функцию и выведем результат:

inp = input("Enter a number: ")
inp = int(inp)

print(f"The result is: {get_factorial_for_loop(inp)}")

Программа предложит пользователю ввести данные. Мы попробуем с 4:

Enter a number: 4
The result is: 24

Можете проверить результат на калькуляторе:

4! = 4 * 3 * 2 * 1 = 24.

Теперь давайте посмотрим, как мы можем вычислить факториал, используя цикл while. Вот наша модифицированная функция:

def get_factorial_while_loop(n):
    result = 1
    while n > 1:
        result = result * n
        n -= 1
    return result

Это очень похоже на цикл for. Только в этот раз, мы движемся от n к 1, что ближе к математическому определению. Протестируем нашу функцию:

inp = input("Enter a number: ")
inp = int(inp)

print(f"The result is: {get_factorial_while_loop(inp)}")

Опять введём 4:

Enter a number: 4
The result is: 24

Хотя считали наоборот, результат получился тот же.

Рассчитывать факториал с помощью цикла легко. Теперь посмотрим, как вычислить факториал с помощью рекурсивной функции.

Вычисляем факториал с помощью рекурсивной функции

Рекурсивная функция – это функция, которая вызывает саму себя. Определение кажется страшным, но потерпите, и вы поймёте, что это значит.

Обычно каждая рекурсивная функция состоит из двух основных компонентов: базового варианта и рекурсивного шага.

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

Без базового случая или с неправильным базовым случаем ваша рекурсивная функция может выполняться бесконечно, вызывая переполнение.

Рекурсивные шаги, как следует из названия, являются рекурсивной частью функции, где вся задача преобразуется в нечто меньшее. Если рекурсивный шаг не позволяет уменьшить задачу, то рекурсия опять-таки может выполняться бесконечно.

Рассмотрим повторяющуюся часть факториалов:

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

Также мы знаем, что:

4 * 3 * 2 * 1 = 4!

Другими словами, 5! = 5 * 4!, 4! = 4 * 3! и так далее.

Таким образом, мы можем сказать, что n! = n * (n-1)!. Это будет рекурсивный шаг нашего факториала!

Факториальная рекурсия заканчивается, когда она достигает 1. Это будет наш базовый случай. Мы вернем 1, если n равно 1 или меньше, покрывая нулевой ввод.

Взглянем на нашу рекурсивную факторную функцию:

def get_factorial_recursively(n):
    if n <= 1:
        return 1
    else:
        return n * get_factorial_recursively(n-1)

Как вы видите, блок if воплощает наш базовый вариант, в то время как блок else охватывает рекурсивный шаг.

Протестируем функцию:

inp = input("Enter a number: ")
inp = int(inp)

print(f"The result is: {get_factorial_recursively(inp)}")

В этот раз введём 3:

Enter a number:3
The result is: 6

В итоге тот же результат. Но на этот код более сложный:

Когда мы вводим данные, функция проверит блок if, и, поскольку 3 больше 1, она перейдет к блоку else. В этом блоке мы видим строчку return n * get_factorial_recursively(n-1).

Мы знаем значение n, оно равно 3, но get_factorial_recursively(n-1) еще предстоит его вычислить.

Затем программа вызывает ту же функцию еще раз, но на этот раз наша функция принимает 2 в качестве параметра. Он проверяет блок if, переходит к блоку else и снова встречается с последней строкой. Теперь текущее значение n равно 2, но программа все равно должна вычислить get_factorial_recursively(n-1).

Поэтому он снова вызывает функцию, но на этот раз блок if, или, скорее, базовый класс, успешно возвращает 1 и выходит из рекурсии.

Следуя тому же шаблону, он возвращает каждый результат функции, умножая текущий результат на предыдущий n и возвращая его для предыдущего вызова функции. Другими словами, наша программа сначала доходит до нижней части факториала (который равен 1), затем идёт вверх, умножая на каждом шаге.

Также удаляет функцию из стека вызовов одну за другой, пока не будет возвращен конечный результат n * (n-1).

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

Заключение

В этой статье мы рассмотрели, как вычислять факториалы с использованием циклов for и while. Мы также узнали, что такое рекурсия и как вычислять факториал с помощью рекурсии.

Если вам понравилась рекурсия и вы хотите больше практиковаться, попробуйте вычислить последовательность Фибоначчи с помощью рекурсии! И если у вас есть какие-либо вопросы или мысли по поводу нашей статьи, не стесняйтесь делиться ими в разделе комментариев.

Просмотры: 1 904

Introduction

By definition, a factorial is the product of a positive integer and all the positive integers that are less than or equal to the given number. In other words, getting a factorial of a number means to multiply all whole numbers from that number, down to 1.

0! equals 1 as well, by convention.

A factorial is denoted by the integer and followed by an exclamation mark.

5! denotes a factorial of five.

And to calculate that factorial, we multiply the number with every whole number smaller than it, until we reach 1:

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

Keeping these rules in mind, in this tutorial, we will learn how to calculate the factorial of an integer with Python, using loops and recursion. Let’s start with calculating the factorial using loops.

Calculating Factorial Using Loops

We can calculate factorials using both the while loop and the for loop. The general process is pretty similar for both. All we need is a parameter as input and a counter.

Let’s start with the for loop:

def get_factorial_for_loop(n):
    result = 1
    if n > 1:
        for i in range(1, n+1):
            result = result * i
        return result
    else:
        return 'n has to be positive'

You may have noticed that we are counting starting from 1 to the n, whilst the definition of factorial was from the given number down to 1. But mathematically:

$$
1 * 2 * 3 * 4 … * n = n * (n-1) * (n-2) * (n-3) * (n-4) … * (n — (n-1))
$$

To simplify, (n - (n-1)) will always be equal to 1.

That means that it doesn’t matter in which direction we’re counting. It can start from 1 and increase towards the n, or it can start from n and decrease towards 1. Now that’s clarified, let’s start breaking down the function we’ve just wrote.

Our function takes in a parameter n which denotes the number we’re calculating a factorial for. First, we define a variable named result and assign 1 as a value to it.

Why assign 1 and not 0 you ask?

Because if we were to assign 0 to it then all the following multiplications with 0, naturally would result in a huge 0.

Then we start our for loop in the range from 1 to n+1. Remember, the Python range will stop before the second argument. To include the last number as well, we simply add an additional 1.

Inside the for loop, we multiply the current value of result with the current value of our index i.

Finally, we return the final value of the result. Let’s test our function print out the result:

inp = input("Enter a number: ")
inp = int(inp)

print(f"The result is: {get_factorial_for_loop(inp)}")

If you’d like to read more about how to get user input, read our Getting User Input in Python.

It will prompt the user to give input. We’ll try it with 4:

Enter a number: 4
The result is: 24

You can use a calculator to verify the result:

4! is 4 * 3 * 2 * 1, which results 24.

Now let’s see how we can calculate factorial using the while loop. Here’s our modified function:

def get_factorial_while_loop(n):
    result = 1
    while n > 1:
        result = result * n
        n -= 1
    return result

This is pretty similar to the for loop. Except for this time we’re moving from n towards the 1, closer to the mathematical definition. Let’s test our function:

inp = input("Enter a number: ")
inp = int(inp)

print(f"The result is: {get_factorial_while_loop(inp)}")

We’ll enter 4 as an input once more:

Enter a number: 4
The result is: 24

Although the calculation was 4 * 3 * 2 * 1 the final result is the same as before.

Calculating factorials using loops was easy. Now let’s take a look at how to calculate the factorial using a recursive function.

Calculating Factorial Using Recursion

A recursive function is a function that calls itself. It may sound a bit intimidating at first but bear with us and you’ll see that recursive functions are easy to understand.

In general, every recursive function has two main components: a base case and a recursive step.

Base cases are the smallest instances of the problem. Also a break, a case that will return a value and will get out of the recursion. In terms of factorial functions, the base case is when we return the final element of the factorial, which is 1.

Without a base case or with an incorrect base case, your recursive function can run infinitely, causing an overflow.

Recursive steps — as the name implies- are the recursive part of the function, where the whole problem is transformed into something smaller. If the recursive step fails to shrink the problem, then again recursion can run infinitely.

Consider the recurring part of the factorials:

• 5! is 5 * 4 * 3 * 2 * 1.

But we also know that:

• 4 * 3 * 2 * 1 is 4!.

In other words 5! is 5 * 4!, and 4! is 4 * 3! and so on.

So we can say that n! = n * (n-1)!. This will be the recursive step of our factorial!

A factorial recursion ends when it hits 1. This will be our base case. We will return 1 if n is 1 or less, covering the zero input.

Let’s take a look at our recursive factorial function:

def get_factorial_recursively(n):
    if n <= 1:
        return 1
    else:
        return n * get_factorial_recursively(n-1)

As you see the if block embodies our base case, while the else block covers the recursive step.

Let’s test our function:

inp = input("Enter a number: ")
inp = int(inp)

print(f"The result is: {get_factorial_recursively(inp)}")

We will enter 3 as input this time:

Enter a number:3
The result is: 6

We get the same result. But this time, what goes under the hood is rather interesting:

You see, when we enter the input, the function will check with the if block, and since 3 is greater than 1, it will skip to the else block. In this block, we see the line return n * get_factorial_recursively(n-1).

We know the current value of n for the moment, it’s 3, but get_factorial_recursively(n-1) is still to be calculated.

Then the program calls the same function once more, but this time our function takes 2 as the parameter. It checks the if block and skips to the else block and again encounters with the last line. Now, the current value of the n is 2 but the program still must calculate the get_factorial_recursively(n-1).

So it calls the function once again, but this time the if block, or rather, the base class succeeds to return 1 and breaks out from the recursion.

Following the same pattern to upwards, it returns each function result, multiplying the current result with the previous n and returning it for the previous function call. In other words, our program first gets to the bottom of the factorial (which is 1), then builds its way up, while multiplying on each step.

Also removing the function from the call stack one by one, up until the final result of the n * (n-1) is returned.

This is generally how recursive functions work. Some more complicated problems may require deeper recursions with more than one base case or more than one recursive step. But for now, this simple recursion is good enough to solve our factorial problem!

If you’d like to learn more about recursion in Python, read our Guide to Understanding Recursion in Python!

Conclusion

In this article, we covered how to calculate factorials using for and while loops. We also learned what recursion is, and how to calculate factorial using recursion.

If you’ve enjoyed the recursion and want to practice more, try calculating the Fibonacci sequence with recursion! And if you have any questions or thoughts about our article, feel free to share in the comment section.