Как найти факториал через рекурсию - Исправление недочетов и поиск решений вместе с Examum.ru

How can I combine these two functions into one recursive function to have this result:

factorial(6)

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720

This is the current code for my factorial function:

def factorial(n):
   if n < 1:   # base case
       return 1
   else:
       return n * factorial(n - 1)  # recursive call


def fact(n):
   for i in range(1, n+1 ):
       print "%2d! = %d" % (i, factorial(i))

and the output that this code produces is the following:

fact(6)

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720

As you see, the execution of these two functions gives me correct answers, but I just wanted to simplify the two functions to a single recursive function.

asked Dec 21, 2010 at 18:06

We can combine the two functions to this single recursive function:

def factorial(n):
   if n < 1:   # base case
       return 1
   else:
       returnNumber = n * factorial(n - 1)  # recursive call
       print(str(n) + '! = ' + str(returnNumber))
       return returnNumber

answered Dec 21, 2010 at 18:13

pythonFoopythonFoo

2,1943 gold badges15 silver badges17 bronze badges

2 lines of code:

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

Test it:

print fac(4)

Result:

answered May 6, 2014 at 17:52

martynasmartynas

12.1k3 gold badges55 silver badges60 bronze badges

def factorial(n):
    result = 1 if n <= 1 else n * factorial(n - 1)
    print '%d! = %d' % (n, result)
    return result

answered Dec 21, 2010 at 18:12

Will McCutchenWill McCutchen

13k3 gold badges43 silver badges43 bronze badges

a short one:

def fac(n):
    if n == 0:
        return 1
    else:
        return n * fac(n-1)
print fac(0)

answered Dec 17, 2012 at 22:29

IlyasIlyas

591 silver badge1 bronze badge

try this:

def factorial( n ):
   if n <1:   # base case
       print "%2d! = %d" % (n, n)
       return 1
   else:
       temp = factorial( n - 1 )
       print "%2d! = %d" % (n, n*temp)
       return n * temp  # recursive call

One thing I noticed is that you are returning ‘1’ for n<1, that means your function will return 1 even for negative numbers. You may want to fix that.

answered Dec 21, 2010 at 18:11

Vinay PandeyVinay Pandey

1,1293 gold badges16 silver badges33 bronze badges

I’ve no experience with Python, but something like this?

def factorial( n ):
   if n <1:   # base case
       return 1
   else:
       f = n * factorial( n - 1 )  # recursive call
       print "%2d! = %d" % ( n, f )
       return f

Tadeck

131k28 gold badges152 silver badges198 bronze badges

answered Dec 21, 2010 at 18:11

MchlMchl

61.3k9 gold badges117 silver badges120 bronze badges

Is this homework by any chance?

def traced_factorial(n):
  def factorial(n):
    if n <= 1:
      return 1
    return n * factorial(n - 1)
  for i in range(1, n + 1):
    print '%2d! = %d' %(i, factorial(i))

Give PEP227 a read for more details. The short of it is that Python lets you define functions within functions.

answered Dec 21, 2010 at 18:14

D.ShawleyD.Shawley

57.9k10 gold badges98 silver badges113 bronze badges

fac = lambda x: 1 if x == 0 else x * fac(x - 1)

answered Mar 4, 2016 at 10:13

One more

def fact(x):
    if x in {0, 1}:
        return 1
    else:
        return x * fact(x-1)

for x in range(0,10):
    print '%d! = %d' %(x, fact(x))

zganger

3,5721 gold badge9 silver badges13 bronze badges

answered Jul 21, 2011 at 20:49

MattyWMattyW

1,5093 gold badges16 silver badges33 bronze badges

And for the first time calculate the factorial using recursive and the while loop.

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

Although the option that TrebledJ wrote in the comments about using if is better. Because while loop performs more operations (SETUP_LOOP, POP_BLOCK) than if. The function is slower.

def factorial(n):
    if  n >= 1:
        return n * factorial(n - 1)
    return 1

timeit -n 10000 -r 10

while 836 µs ± 11.8 µs per loop
if 787 µs ± 7.22 µs per loop

answered Nov 13, 2018 at 13:09

SzczerskiSzczerski

7799 silver badges10 bronze badges

Can use these 4 lines of code…

   def factorial(n):
        f = lambda n: n * f(n - 1) if n > 1 else 1

        for x in range(n):
            print('{}! = {}'.format(x + 1, factorial(x + 1)))

0 _

10.3k11 gold badges76 silver badges109 bronze badges

answered Jun 4, 2018 at 21:27

Meir KellerMeir Keller

4911 gold badge7 silver badges19 bronze badges

I don’t really know the factorial of negative numbers, but this will work with all n >= 0:

def factorial(n):
    if n >= 0:
        if n == 1 or n == 0:
            return 1
        else:
            n = n * factorial(n-1)
            return n

    return 'error'

answered Jun 28, 2017 at 14:50

In Python 3.8 you can try factorial function itself.

import math
n=int(input())
print(math.factorial(n))

For example:

Input: 5

Output:120

answered Sep 1, 2022 at 15:37

There is always some kind of a loop in recursive functions and some stoping codes which stop the loop:

public int recursivefactorial(int number)
{
    if(number==1)
        return 1;
    else
        return recursivefactorial(number-1)*number;
}

As you can see the fulfilling the if condition leads to the code that actually ends the «loop» and this is the most important part of a recursive function. In contrast, the else part of the condition leads to calling recursivefactorial function once again which is effectively a kind of loop.

Robson

8115 gold badges21 silver badges40 bronze badges

answered Apr 25, 2019 at 6:05

One more =)

#FAC calculation

def fakulteta(x):
    if x!=1:
         return x*fakulteta(x-1)
    return 1


print (fakulteta(12))

answered Apr 23, 2018 at 11:37

Источник

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

Факториал вычисляется по следующей формуле:

Для его нахождения будем использовать рекурсивную функцию. Рекурсивная функция — это функция, которая вызывает сама себя.

Начнем писать программу. Подключим необходимые библиотеки и напишем рекурсивную функцию factorial(n):

#include <stdio.h>

#include <conio.h>

long int factorial(long int n)

{

if (n == 0 || n == 1) return 1;

return n * factorial(n — 1);

}

Разберем функцию подробнее. Будем работать с типом данных long int — это длинный целый тип. Для нашей программы этот тип подходит лучше всего, потому что факториал — чрезвычайно быстрорастущая функция. Условие if (строка 6) — условие остановки рекурсии.

Рассмотрим пример. Допустим необходимо вычислить факториал пяти (n=5). Вызываем функцию factorial(5), условие остановки не срабатывает, переходим к оператору return (строка 7). Умножаем n на то, что вернет функция factorial(n — 1), вычисляем эту функцию: в нее мы передаем число 4 (5-1=4). То есть мы спускаемся на уровень ниже. И так мы будем спускаться вниз да тех пор, пока n не станет равным единице или нулю, тогда сработает условие остановки рекурсии. Функция вернет 1. Единица будет умножена на n (=2), и так, по уровням, будем подниматься наверх, умножая на текущее для конкретного уровня число n то, что вернет функция с уровня, который ниже. В результате мы получим значение факториала.

Примечание. Факториал нуля равен единице (0!=1).

Теперь напишем функцию main():

int main ()

{

long int n;

printf(«Calculation n!nInput n: «);

scanf_s(«%d», &n);

if (n >= 0)

printf(«%d! = %dn», n, factorial(n));

else

printf(«Error. n must be >= 0n»);

_getch();

return 0;

}

В ней мы просим пользователя ввести число n и считываем его с клавиатуры. Далее выполняем проверку: число n должно быть больше или равно нулю. Если условие выполняется, то вычисляем факториал и выводим его значение на экран, если условие не выполняется, то выводим в консоль сообщение об ошибке.

Демонстрация работы программы представлена на рисунке:

Чтобы скачать исходник программы, написанной в этой статье, нажмите на кнопку ниже:

Скачать исходник

Источник

Описание задачи

Программа принимает на вход число и вычисляет факториал этого числа с использованием рекурсивного алгоритма.

Решение задачи

Записываем введенное пользователем число в отдельную переменную.
Передаем это число в качестве аргумента в рекурсивную функцию, которая вычисляет факториал.
Определяем внутри этой функции базовое условие рекурсии: в случае, когда аргумент функции меньше либо равен 1, рекурсивная функция прекращает свою работу и возвращает в качестве результата 1.
В противном случае в качестве результата возвращается число, умноженное на рекурсивную функцию, аргумент которой уменьшен на единицу. И все повторяется заново.
После того, как рекурсивная функция прекратила свою работу, на экран выводится результат.
Конец.

Исходный код

Ниже дан исходный код, который осуществляет нахождение факториала числа при помощи рекурсии. Результаты работы программы также даны ниже.

def factorial(n):
    if (n <= 1):
        return 1
    else:
        return (n * factorial(n-1))
n = int(input("Введите число:"))
print("Факториал числа равен:")
print(factorial(n))

Объяснение работы программы

Пользователь вводит число и оно записывается в переменную n.
Передаем число n в качестве аргумента в рекурсивную функцию, которая вычисляет факториал этого числа.
Задаем базу рекурсии при помощи условия n <= 1 . Если оно выполняется, рекурсивная функция возвращает 1 и ее работа останавливается.
В противном случае функция возвращает n * factorial(n-1) и все повторяется заново.
После того, как функция завершит свою работу, результат выводится на экран.

Результаты работы программы

Пример 1:
Введите число:5
Факториал числа равен:
120
 
Пример 2:
Введите число:9
Факториал числа равен:
362880

Источник

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Like Article

Given a large number N, the task is to find the factorial of N using recursion.

Factorial of a non-negative integer is the multiplication of all integers smaller than or equal to n. For example factorial of 6 is 6*5*4*3*2*1 which is 720.

Examples:

Input : N = 100
Output : 933262154439441526816992388562667004-907159682643816214685929638952175999-932299156089414639761565182862536979-208272237582511852109168640000000000-00000000000000

Input : N = 50
Output : 3041409320171337804361260816606476884-4377641568960512000000000000

Iterative Approach: The iterative approach is discussed in Set 1 of this article. Here, we have discussed the recursive approach.

Recursive Approach: To solve this problem recursively, the algorithm changes in the way that calls the same function recursively and multiplies the result by the number n. Follow the steps below to solve the problem:

If n is less than equal to 2, then multiply n by 1 and store the result in a vector.
Otherwise, call the function multiply(n, factorialRecursiveAlgorithm(n – 1)) to find the answer.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

vector<int> multiply(long int n, vector<int> digits)

{

long int carry = 0;

for (long int i = 0; i < digits.size(); i++) {

long int result

= digits[i] * n + carry;

digits[i] = result % 10;

carry = result / 10;

}

while (carry) {

digits.push_back(carry % 10);

carry = carry / 10;

}

return digits;

}

vector<int> factorialRecursiveAlgorithm(

long int n)

{

if (n <= 2) {

return multiply(n, { 1 });

}

return multiply(

n, factorialRecursiveAlgorithm(n - 1));

}

int main()

{

long int n = 50;

vector<int> result

= factorialRecursiveAlgorithm(n);

for (long int i = result.size() - 1; i >= 0; i--) {

cout << result[i];

}

cout << "n";

return 0;

}

Java

import java.util.*;

class GFG{

static Integer []multiply(int n, Integer []digits)

{

int carry = 0;

for (int i = 0; i < digits.length; i++) {

int result

= digits[i] * n + carry;

digits[i] = result % 10;

carry = result / 10;

}

LinkedList<Integer> v = new LinkedList<Integer>();

v.addAll(Arrays.asList(digits));

while (carry>0) {

v.add(new Integer(carry % 10));

carry = carry / 10;

}

return v.stream().toArray(Integer[] ::new);

}

static Integer []factorialRecursiveAlgorithm(

int n)

{

if (n <= 2) {

return multiply(n, new Integer[]{ 1 });

}

return multiply(

n, factorialRecursiveAlgorithm(n - 1));

}

public static void main(String[] args)

{

int n = 50;

Integer []result

= factorialRecursiveAlgorithm(n);

for (int i = result.length - 1; i >= 0; i--) {

System.out.print(result[i]);

}

System.out.print("n");

}

C#

using System;

using System.Collections.Generic;

using System.Linq;

class GFG

{

static int[] multiply(int n, int[] digits)

{

int carry = 0;

for (int i = 0; i < digits.Length; i++)

{

int result

= digits[i] * n + carry;

digits[i] = result % 10;

carry = result / 10;

}

LinkedList<int> v = new LinkedList<int>();

foreach (int i in digits)

{

v.AddLast(i);

}

while (carry > 0)

{

v.AddLast((int)(carry % 10));

carry = carry / 10;

}

return v.ToArray();

}

static int[] factorialRecursiveAlgorithm(

int n)

{

if (n <= 2)

{

return multiply(n, new int[] { 1 });

}

return multiply(

n, factorialRecursiveAlgorithm(n - 1));

}

public static void Main()

{

int n = 50;

int[] result = factorialRecursiveAlgorithm(n);

for (int i = result.Length - 1; i >= 0; i--)

{

Console.Write(result[i]);

}

Console.Write("n");

}

Python3

def multiply(n, digits):

carry = 0

for i in range(len(digits)):

result = digits[i] * n + carry

digits[i] = result % 10

carry = result // 10

while (carry):

digits.append(carry % 10)

carry = carry // 10

return digits

def factorialRecursiveAlgorithm(n):

if (n <= 2):

return multiply(n, [1])

return multiply(

n, factorialRecursiveAlgorithm(n - 1))

if __name__ == "__main__":

n = 50

result = factorialRecursiveAlgorithm(n)

for i in range(len(result) - 1, -1, -1):

print(result[i], end="")

Javascript

<script>

function multiply(n, digits)

{

var carry = 0;

for (var i = 0; i < digits.length; i++) {

var result

= digits[i] * n + carry;

digits[i] = result % 10;

carry = parseInt(result / 10);

}

while (carry>0) {

digits.push(carry % 10);

carry = parseInt(carry / 10);

}

return digits;

}

function factorialRecursiveAlgorithm(

n)

{

if (n <= 2) {

return multiply(n, [ 1 ]);

}

return multiply(

n, factorialRecursiveAlgorithm(n - 1));

}

var n = 50;

var result = factorialRecursiveAlgorithm(n);

for (var i = result.length - 1; i >= 0; i--) {

document.write(result[i]);

}

document.write("<br>");

</script>

Output

30414093201713378043612608166064768844377641568960512000000000000

Time Complexity: O(n*log(n))
Auxiliary Space: O(K), where K is the maximum number of digits in the output

Last Updated :
09 Jan, 2023

Like Article

Save Article

Источник

На чтение 3 мин Просмотров 4.5к. Опубликовано 28.02.2023

Содержание

Введение
Вычисление факториала циклом while
Цикл while
Цикл for
Вычисление факториала Рекурсией
Вычисление факториала методом factorial()
Заключение

Введение

В ходе статьи рассмотрим 3 способа вычислить факториал в Python.

Вычисление факториала циклом while

Цикл while

Для начала дадим пользователю возможность ввода числа и создадим переменную factorial равную единице:

number = int(input('Введите число: '))
factorial = 1

Как мы знаем, факториал – это произведение натуральных чисел от единицы до числа n. Следовательно создадим цикл, который не закончится, пока введённое пользователем число больше единицы. Внутри цикла увеличиваем значение в переменной factorial умножая его на переменную number, после чего уменьшаем значение в number на единицу:

number = int(input('Введите число: '))
factorial = 1

while number > 1:
    factorial = factorial * number
    number = number - 1

print(factorial)

# Введите число: 10
# 3628800

Цикл for

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

number = int(input('Введите число: '))
factorial = number

for i in range(1, number):
    factorial = factorial * i

print(factorial)

# Введите число: 5
# 120

Вычисление факториала Рекурсией

Для вычисления факториала про помощи рекурсии, создадим функцию factorial(), и в качестве аргумента передадим number:

Внутри функции добавим условие, что если переданное число в аргумент number равняется единице, то возвращаем его. Если же условие не сработало, то вернётся аргумент number умноженный на вызов функции factorial() с передачей аргумента number – 1:

def factorial(number):
    if number == 1:
        return number
    else:
        return number * factorial(number - 1)

Дадим пользователю возможность ввода, вызовем функцию и выведем результат в консоль:

def factorial(number):
    if number == 1:
        return number
    else:
        return number * factorial(number - 1)


print(factorial(int(input('Введите число: '))))

# Введите число: 7
# 5040

Вычисление факториала методом factorial()

В стандартном модуле math есть специальный метод для вычисления факториала под названием factorial(). Используем его для нахождения факториала:

from math import factorial

number = int(input('Введите число: '))

print(factorial(number))

# Введите число: 4
# 24

Заключение

В ходе статьи мы с Вами рассмотрели целых 3 способа вычислить факториал в Python. Надеюсь Вам понравилась статья, желаю удачи и успехов! 🙂

Admin

Источник