Dado un gran número N , la tarea es encontrar el factorial de N usando recursividad .
El factorial de un entero no negativo es la multiplicación de todos los enteros menores o iguales a n. Por ejemplo, el factorial de 6 es 6*5*4*3*2*1, que es 720.
Ejemplos:
Input : N = 100
Output : 933262154439441526816992388562667004-907159682643816214685929638952175999-932299156089414639761565182862536979-208272237582511852109168640000000000-00000000000000Entrada: N = 50
Salida: 3041409320171337804361260816606476884-4377641568960512000000000000
Enfoque iterativo: El enfoque iterativo se analiza en el Conjunto 1 de este artículo . Aquí, hemos discutido el enfoque recursivo.
Enfoque recursivo: para resolver este problema recursivamente, el algoritmo cambia en la forma en que llama recursivamente a la misma función y multiplica el resultado por el número n. Siga los pasos a continuación para resolver el problema:
- Si n es menor que igual a 2, entonces multiplique n por 1 y almacene el resultado en un vector .
- De lo contrario, llame a la función multiplicar (n, factorialRecursiveAlgorithm (n – 1)) para encontrar la respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// MUltiply the number x with the number
// represented by res array
vector<int> multiply(long int n, vector<int> digits)
{
// Initialize carry
long int carry = 0;
// One by one multiply n with
// individual digits of res[]
for (long int i = 0; i < digits.size(); i++) {
long int result
= digits[i] * n + carry;
// Store last digit of 'prod' in res[]
digits[i] = result % 10;
// Put rest in carry
carry = result / 10;
}
// Put carry in res and increase result size
while (carry) {
digits.push_back(carry % 10);
carry = carry / 10;
}
return digits;
}
// Function to recursively calculate the
// factorial of a large number
vector<int> factorialRecursiveAlgorithm(
long int n)
{
if (n <= 2) {
return multiply(n, { 1 });
}
return multiply(
n, factorialRecursiveAlgorithm(n - 1));
}
// Driver Code
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
// Java program for the above approach
import java.util.*;
class GFG{
// MUltiply the number x with the number
// represented by res array
static Integer []multiply(int n, Integer []digits)
{
// Initialize carry
int carry = 0;
// One by one multiply n with
// individual digits of res[]
for (int i = 0; i < digits.length; i++) {
int result
= digits[i] * n + carry;
// Store last digit of 'prod' in res[]
digits[i] = result % 10;
// Put rest in carry
carry = result / 10;
}
// Put carry in res and increase result size
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);
}
// Function to recursively calculate the
// factorial of a large number
static Integer []factorialRecursiveAlgorithm(
int n)
{
if (n <= 2) {
return multiply(n, new Integer[]{ 1 });
}
return multiply(
n, factorialRecursiveAlgorithm(n - 1));
}
// Driver Code
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");
}
}
// This code is contributed by 29AjayKumar
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG
{
// MUltiply the number x with the number
// represented by res array
static int[] multiply(int n, int[] digits)
{
// Initialize carry
int carry = 0;
// One by one multiply n with
// individual digits of res[]
for (int i = 0; i < digits.Length; i++)
{
int result
= digits[i] * n + carry;
// Store last digit of 'prod' in res[]
digits[i] = result % 10;
// Put rest in carry
carry = result / 10;
}
// Put carry in res and increase result size
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();
}
// Function to recursively calculate the
// factorial of a large number
static int[] factorialRecursiveAlgorithm(
int n)
{
if (n <= 2)
{
return multiply(n, new int[] { 1 });
}
return multiply(
n, factorialRecursiveAlgorithm(n - 1));
}
// Driver Code
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");
}
}
// This code is contributed by gfgking
Javascript
<script>
// javascript program for the above approach
// MUltiply the number x with the number
// represented by res array
function multiply(n, digits)
{
// Initialize carry
var carry = 0;
// One by one multiply n with
// individual digits of res
for (var i = 0; i < digits.length; i++) {
var result
= digits[i] * n + carry;
// Store last digit of 'prod' in res
digits[i] = result % 10;
// Put rest in carry
carry = parseInt(result / 10);
}
// Put carry in res and increase result size
while (carry>0) {
digits.push(carry % 10);
carry = parseInt(carry / 10);
}
return digits;
}
// Function to recursively calculate the
// factorial of a large number
function factorialRecursiveAlgorithm(
n)
{
if (n <= 2) {
return multiply(n, [ 1 ]);
}
return multiply(
n, factorialRecursiveAlgorithm(n - 1));
}
// Driver Code
var n = 50;
var result = factorialRecursiveAlgorithm(n);
for (var i = result.length - 1; i >= 0; i--) {
document.write(result[i]);
}
document.write("<br>");
// This code is contributed by shikhasingrajput
</script>
Python3
# Python 3 program for the above approach # MUltiply the number x with the number # represented by res array def multiply(n, digits): # Initialize carry carry = 0 # One by one multiply n with # individual digits of res[] for i in range(len(digits)): result = digits[i] * n + carry # Store last digit of 'prod' in res[] digits[i] = result % 10 # Put rest in carry carry = result // 10 # Put carry in res and increase result size while (carry): digits.append(carry % 10) carry = carry // 10 return digits # Function to recursively calculate the # factorial of a large number def factorialRecursiveAlgorithm(n): if (n <= 2): return multiply(n, [1]) return multiply( n, factorialRecursiveAlgorithm(n - 1)) # Driver Code if __name__ == "__main__": n = 50 result = factorialRecursiveAlgorithm(n) for i in range(len(result) - 1, -1, -1): print(result[i], end="")
Producción
30414093201713378043612608166064768844377641568960512000000000000
Complejidad de tiempo: O(n)
Espacio auxiliar: O(K), donde K es el número máximo de dígitos en la salida