Как найти факториал с помощью рекурсии — Сайт, где вы сможете решить свои вопросы

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

5

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:

24

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

1

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

1

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

1

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

2

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

1

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

1

Источник

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

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

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

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

Разберем функцию подробнее. Будем работать с типом данных 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():

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

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

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

Словить исходник

Источник

30414093201713378043612608166064768844377641568960512000000000000

Источник

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

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

Источник

Рекурсивные методы[править]

Примеры реализаций рекурсивных функций для вычисления факториала.

Pascal[править]

  function fact(n : integer) : longint;
  begin
    if n <= 1 then fact := 1 else fact := n * fact(n - 1);
  end;

Delphi[править]

С подключённым модулем System.Math

  function fact(n : integer) : int64;
  begin
    Result:=IfThen(n <= 1, 1, n * fact(n - 1));
  end;

C/C++[править]

  int factorial(int n) {
   return n<=1 ? 1 : n * factorial(n-1);
  }

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

Common Lisp[править]

 (defun factorial (n)
   (if (= n 0)
       1
       (* (factorial (- n 1)) n)))

Clojure[править]

 (defn fact[x]
   (if (<= x 1) 1 (* x  (fact (- x 1))  )))

Forth[править]

  : factorial ( n -- n! )
    dup 0= if
      drop 1
    else
      dup 1- recurse *
    endif ;

Go[править]

  func Factorial(n uint) uint {
    if n == 0 {
        return 1
    }
    return n * Factorial(n - 1)
  }

Scheme[править]

(define (factorial n)
   (if (= n 0)
       1
       (* (factorial (- n 1)) n)))

Ruby[править]

def factorial n
  n > 1 ? n * factorial(n - 1) : 1
end

Rust[править]

fn factorial_recursive (n: u64) -> u64 {
	match n {
		0 => 1,
		_ => n * factorial_recursive(n-1)
	}
}
 
fn main () {
	println!("{}", factorial_recursive(5))
}

PHP[править]

function factorial($n)
{
  return $n ? $n * factorial($n-1) : 1;
}

Perl[править]

#!/usr/bin/perl
sub factorial {
    my $n = shift;
    if ($n==0) {
        return 1;
    } else {
        return $n*factorial($n-1);
    }
}
print factorial(shift);

или однострочник

perl -e 'sub f{ $_[0] <= 1 ? 1 : $_[0] * f($_[0] - 1)}; print f(shift)' number

Simula[править]

integer procedure factorial (n); integer n;
  factorial := if n=0 then 1 else n*factorial(n-1);
begin
  integer n;
  n:=10
  outint(n,5);
  outtext("! = ");
  outint(factorial(n),10);
  outimage;
end

Smalltalk[править]

factorial
    "Answer the factorial of the receiver."
    self = 0 ifTrue: [^ 1].
    self > 0 ifTrue: [^ self * (self - 1) factorial].
    self error: ’Not valid for negative integers’

Swift[править]

func factorial(_ n: Int) -> Int {
    return n == 0 ? 1 : n * factorial(n - 1)
}

Algol 68[править]

PROC factorial = (INT n) INT:
BEGIN
   IF n=0 THEN
      1
   ELSE
      n*factorial(n-1)
   FI
END;
print (factorial(10))

Ada[править]

function Factorial (N: Natural) return Natural is
begin
   if N = 0 then
      return 1;
   else
      return N * Factorial(N - 1);
   end if;
end Factorial;

или используя «if expression» (Ada 2012)

function Factorial (N: Natural) return Natural is
begin
   return (if N = 0 then 1 else N * Factorial(N - 1));
end Factorial;

LaTeX[править]

documentclass{article}
usepackage{ifthen}
newcounter{multi} newcounter{multa}
newcommand{mult}[2]{ setcounter{multi}{1} setcounter{multa}{#1}
 whiledo{themulti < #2}{ addtocounter{multa}{#1} stepcounter{multi} } }
newcounter{faki} newcounter{faka}
newcommand{fac}[1]{
 setcounter{faka}{1} setcounter{faki}{2}
 whiledo{thefaki < #1}{
     mult{thefaka}{thefaki}
     setcounter{faka}{themulta}
     stepcounter{faki}}
 mult{thefaka}{thefaki} themulta}
begin{document}
 Huge $10!=fac{10}$
end{document}

Java и C#[править]

Рекурсивный метод:

public int fact(int num) {
     return ((num > 1) ? num * fact(num - 1) : 1);
}

Если вы переживаете, что стек может быть переполнен, то используйте не рекурсивный метод:

public static uint Factorial(uint num)
{
     uint fact = 1;
     while (num > 1) fact *= num--;
     return fact;
}

JavaScript[править]

var factorial = function factorialis (m) {
    var n = parseInt(m);
    return (n < 0 || m != n) ? NaN : (n == 0 ? 1 : n * factorialis(n - 1));
}

CoffeeScript[править]

factorial = (n) -> !n and 1 or n * factorial(n - 1);

Python[править]

def factorial(x):
    return x * factorial(x - 1) if x > 1 else 1

или

factorial = lambda x: x and factorial(x - 1) * x or 1

или

import math
math.factorial(x)

или

from functools import reduce
factorial = reduce(lambda x, y: x * y, range(1, n + 1)

Refal[править]

Factorial {
    0 = 1;
    s.Value = <Mul s.Value <Factorial <Sub s.Value 1>>>;
}

Haskell[править]

factorial :: Integer -> Integer
factorial 0 = 1
factorial n | n > 0 = n * factorial (n - 1)
factorial _ = error "Факториал не определен для отрицательных чисел"

или

factorial :: Integer -> Integer
factorial n = product [1..n]

D[править]

long Factorial(int n)
{
    if (n <= 1)
        return 1;
    return n * Factorial(n - 1);
}

Нерекурсивные методы[править]

Примеры реализаций нерекурсивных функций для вычисления факториала.

Pascal[править]

  function factorial(n : integer) : longint;
  var
    i : integer;
    f : longint;
  begin
      f := 1;
      for i := 2 to n do
        f := f * i;
      factorial := f
  end;

Perl[править]

#!/usr/bin/perl
  sub factorial { 
      my $f=1; 
      my @fct= $f .. $_[0]; 
      foreach (@fct) {$f*=$_;} $f; 
      }

C/C++[править]

  int factorial(int n) {
      int result = 1;

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

Java и C#[править]

public static int factorial(int num) {
	int fact = 1;
	for (; num > 1; fact *= num--);
        return fact;
}

JavaScript[править]

const factorial = (n) => {
    if (n < 0) return NaN;
    let result = 1;
    for (let i = 1; i <= n; i++) {
	    result *= i;
    }
    return result;
}

CoffeeScript[править]

factorial = (n) ->
  res = 1
  res *= n-- while n > 1
  res

или

factorial = (n) -> [1..n].reduce (x,y) -> x * y || 1

Lisp[править]

 (defun factorial (n)
    (if (< n 1)
      1
      (do ((f 1) (i 2 (1+ i)))
        ((> i n) f)
        (setq f (* f i)))))

Fortran[править]

integer function fact (n)
integer n
fact = 1
do i = 1,n
    fact = fact * i
enddo
return
end
program factorial
integer fact
external fact
n = 10
write (*,*) n,"! = ",fact(n)
end program factorial

Unix Shell[править]

#!/bin/sh
result=1
for (( factor=$1 ; $factor ; factor=$factor-1 ))
do
     let -i result=$result*$factor
done
echo $result

CMD Shell[править]

@echo off

set /p n=" n : "

set f=1 & for /l %%i in (1,1,%n%) do set /a f=%%i*f 

echo %f%

pause&exit

PHP[править]

function factorial($n)
{
  $result = 1;

  for ($i=2; $i<=$n; $i++)
    $result *= $i;

  return $result;
}

или

function factorial($n) {
  return ($n <= 1) ? 1 : array_product(range(1,$n));
}

Cobol[править]

identification division.
program-id. factorial.
environment division.
data division.
working-storage section.
77 result pic 9(8).
77 n pic 9(8).
77 i pic 9(8).
procedure division.
main-line.
        display "Enter a positive number: " with no advancing
        accept n
        move 1 to result.
        perform varying i from 1 by 1 until i>n
                 multiply result by i giving result
        end-perform
        display "Factorial(" n ")= " result
        stop run.

Basic[править]

input "N = "; n
f=1
for i = 1 to n
    f=f*i
next i
print n;"! = ";f

Программируемые калькуляторы «Электроника»[править]

Примечание: команда ВП по адресу 00. превращает 0 в 1, позволяя корректно вычислять 0! = 1.

Вариант № 1[править]

С использованием счётчика в адресуемом регистре (в качестве r следует выбрать один из регистров: 0, 1, 2, 3).

00. ВП     01. Пr     02. 1      03. ИПr    04. ×      05. FLr    06. 03     07. С/П

Вариант № 2[править]

С использованием регистров стека X, Y, Z (значение, находившееся в регистре Y, сохраняется).

00. ВП     01. В↑     02. КНОП   03. 1      04. −      05. Fx≠0   06. 11     07. ×      08. FВx    09. БП
10. 03     11. F⟳     12. С/П

Вариант № 3[править]

С использованием регистров стека X, Y, Z, T (т. е. стек используется целиком).

00. ВП     01. ↔      02. FВx    03. В↑     04. FВx    05. 1      06. -      07. ×      08. Fx=0   09. 03
10. ↔      11. С/П

AT&T x86 Assembler[править]

factorial.s:      .globl factorial
                  factorial:
                          movl      $1, %eax
                          jmp      .L2
                  .L3:
                          imull     2(%esp), %eax
                          decl      78(%esp)
                  .L2:
                          cmpl      $1, 4(%esp)
                          jg       .L3
                          ret
factorial-main.c: #include <stdio.h>
                  extern int factorial (int n);
                  int main () {
                      int n = 10;
                      printf ("%d! = %dn", n, factorial (n));
                  }

gcc factorial-main.c factorial.s

Refal+[править]

$func Factorial s.n = s.fact;
Factorial s.n =
    1 s.n $iter <Mult s.fact s.n> <Sub s.n 1> :: s.fact s.n,
    s.n : 0 =
    s.fact;

Ruby[править]

def factorial n
  (1..n).inject(:*) || 1
end

Без итераторов:

def factorial n
  f = 1
  for i in 2..n
    f *= i
  end
  f
end

Python[править]

def factorial(x):
    return reduce(lambda x, y : x * y, xrange(1, x + 1), 1)

С while циклом:

def factorial(x):
    res = 1
    while x > 0:
        res *= x
        x -= 1
    return res

С циклом for:

def factorial(a):
    if a == 0 or a == 1:
        return 1
    else:
        result = 1
        for i in range(2, a + 1):
            result *= i
        return result

J[править]

factorial=: */@(>:@i.)

RSL (Object RSL)[править]

Macro factorial (n)
   if (n < 0)
      fact = "Enter a positive number";
   elif (n == 0)
      fact = 1;
   else
      fact = i = 1;
      while (i <= n)
         fact = fact*i;
         i = i + 1;
      end;
   end;
   return fact;
end;

Ada[править]

function Factorial (N: Natural) return Natural is
   Acc : Natural := 1;
begin
   for I in 2 .. N loop
      Acc := Acc * I;
   end loop;
   return Acc;
end Factorial;

См. также[править]

• Язык Си в примерах/Факториал

Источник