Программа для расчета значения nCr с использованием рекурсии

Учитывая два числа N и r , найдите значение ^N C _r с помощью рекурсии

Примеры :

Input: N = 5, r = 2
Output: 10
Explanation: The value of 5C2 is 10

Input: N = 3, r = 1
Output: 3

Подход 1. Один очень интересный способ найти C(n,r) — это рекурсивный метод, основанный на рекурсивном уравнении.

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

Ниже приведена реализация вышеуказанного подхода следующим образом:

Time Complexity: O(2^n), Auxilary Space: O(n)

Подход 2 : Другая идея просто основана на приведенной ниже формуле.

^NC_r = N! / (r! * (N-r)!)
Also, 
^NC_r-1 = N! / ( (r-1)! * (N – (r-1))! )

Hence,

• ^NC_r * r! * (N – r)! = ^NC_r-1  * (r-1)! * (N – (r-1))!
• ^NC_r * r * (N-r)! = ^NC_r-1  * (N-r+1)!                          [eliminating (r – 1)! from both side]
• ^NC_r * r = ⁿC_r-1  * (N-r+1)

Следовательно,

^NC_r = ^NC_r-1 * (N-r+1) / r

Ниже приведена реализация вышеуказанного подхода:

Time Complexity: O(N!), Auxiliary Space: O(1)