Programa para calcular el valor de nCr usando Recursion

Dados dos números N y r , encuentre el valor de ^N C _r usando recursividad

Ejemplos :

Entrada : N = 5, r = 2
Salida : 10
Explicación : El valor de 5C2 es 10

Entrada : N = 3, r = 1
Salida : 3

Enfoque 1: una forma muy interesante de encontrar C(n,r) es el método recursivo que se basa en la ecuación recursiva.

C(n,r) = C(n-1,r-1) + C(n-1,r)

A continuación se muestra la implementación del enfoque anterior de la siguiente manera:

#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the value of nCr
// using recursion
 
int comb(int n,int r){
   if(n<r){
       return 0;
   }
   if(r == 0){
       return 1;
   }
   if(r == 1){
       return n;
   }
   if(n == 1){
       return 1;
   }
   return comb(n-1,r-1)+comb(n-1,r);
}
 
// Driver code
int main(){
   int n = 10,r = 5;
   cout << comb(n,r);
}

<script>
//Javascript code to implement above approach
 
// Function to calculate the value of nCr
// using recursion
 
function comb(n, r){
   if( n<r ){
       return 0;
   }
   if(r == 0){
       return 1;
   }
   if(r == 1){
       return n;
   }
   if(n == 1){
       return 1;
   }
   return comb(n-1,r-1) + comb(n-1,r);
}
 
// Driver code
 
let n = 5, r = 3;
document.write(comb(n,r));
  
// </script>

using System;
 
public class GFG{
 
  // Function to calculate the value of nCr
  // using recursion
  static int comb(int n, int r)
  {
    if(n<r){
       return 0;
    }
    if(r == 0){
       return 1;
    }
    if(r == 1){
       return n;
    }
    if(n == 1){
       return 1;
    }
    return comb(n-1,r-1)+comb(n-1,r);
  }
 
  // Driver code
  static public void Main (){
 
    int n = 5, r = 3;
    Console.WriteLine(comb(n, r));
  }
}

// Java code for the above approach
import java.io.*;
class GFG {
 
  // Function to calculate the value of nCr
  // using recursion
  static int comb(int n, int r)
  {
     if(n<r){
       return 0;
     }
     if(r == 0){
         return 1;
     }
     if(r == 1){
         return n;
     }
     if(n == 1){
         return 1;
     }
     return comb(n-1,r-1)+comb(n-1,r);
  }
 
  public static void main(String[] args)
  {
    int n = 5, r = 3;
 
    System.out.println(comb(n, r));
  }
}

252

Complejidad de tiempo: O(2^n), Espacio auxiliar : O(n)

Enfoque 2 : otra idea se basa simplemente en la siguiente fórmula.

^N C _r = N! / (r! * (Nr)!)
Además, 
^N C _r-1 = N! / ( (r-1)! * (N – (r-1))! )

Por eso,

• ^N C _r * r! * (N – r)! = ^N C _r-1  * (r-1)! * (N – (r-1))!
• ^N C _r * r * (Nr)! = ^N C _r-1  * (N-r+1)! [eliminando (r – 1)! de ambos lados]
• ^norte C _{r *} ^r = norte C _r-1  * (N-r+1)

Por lo tanto,

^norte C _r = norte C _{r-1 * (} ^N -r+1) / r

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the value of nCr
// using recursion
int nCr(int N, int r)
{
    int res = 0;
    if (r == 0) {
        return 1;
    }
    else {
        res = nCr(N, r - 1)
              * (N - r + 1) / r;
    }
    return res;
}
 
// Driver code
int main()
{
    int N = 5, r = 3;
    cout << nCr(N, r);
    return 0;
}

// Java code for the above approach
import java.io.*;
class GFG {
 
  // Function to calculate the value of nCr
  // using recursion
  static int nCr(int N, int r)
  {
    int res = 0;
    if (r == 0) {
      return 1;
    }
    else {
      res = nCr(N, r - 1) * (N - r + 1) / r;
    }
    return res;
  }
 
  public static void main(String[] args)
  {
    int N = 5, r = 3;
 
    System.out.println(nCr(N, r));
  }
}
 
// This code is contributed by Potta Lokesh

# Python code to implement above approach
 
# Function to calculate the value Of nCr
# using recursion
def nCr(N, r):
    res = 0
    if(r == 0):
        return 1
    else:
        res = nCr(N, r-1)
* (N-r + 1) / r
    return res
 
 
# Driver code
if __name__ == "__main__":
    N = 5
    r = 3
    print(int(nCr(N, r)))

using System;
 
public class GFG{
 
  // Function to calculate the value of nCr
  // using recursion
  static int nCr(int N, int r)
  {
    int res = 0;
    if (r == 0) {
      return 1;
    }
    else {
      res = nCr(N, r - 1)
        * (N - r + 1) / r;
    }
    return res;
  }
 
  // Driver code
  static public void Main (){
 
    int N = 5, r = 3;
    Console.WriteLine(nCr(N, r));
  }
}
 
// This code is contributed by hrithikgarg03188.

<script>
//Javascript code to implement above approach
 
// Function to calculate the value of nCr
// using recursion
function nCr(N, r)
{
    let res = 0;
    if (r == 0) {
        return 1;
    }
    else {
        res = nCr(N, r - 1)
              * (N - r + 1) / r;
    }
    return res;
}
 
// Driver code
 
let N = 5, r = 3;
document.write(nCr(N,r));
     
// This code is contributed by Taranpreet
// </script>

10

Complejidad de tiempo : O(N!), Espacio auxiliar : O(1)