Как написать рекурсивную функцию для комбинации

Question

Я перехожу к рекурсивным функциям, и я понимаю, как писать базовые, но у меня есть вопрос о моем учебном пособии, который я не понимаю.

. Напишите код для рекурсивной функции с именем Combinations, которая вычисляет nCr. Предположим, что Ncr может быть вычислена следующим образом:

nCr = 1 if r = 0 or if r = n and 
nCr = (n-1)C(r-1) + (n-1)Cr 

Может кто-то пожалуйста, помогите мне через это или объяснить с точки зрения непрофессионала? Спасибо!

Answer 1

Вопрос действительно содержит всю информацию. В нем рассказывается, как вычислить nCr, и что много времени вы вычисляете, вычисляя еще один nCr (с меньшими аргументами). Таким образом, ваши функции могут выглядеть так:

int nCr(n, r) { 
    if (r == 0 || r == n) return 1; // stop recursion, we know the answer. 
    return nCr(n-1, r-1) + nCr(n-1, r); // the answer is made of the sum of two "easier" ones 
} 

Это переводится как буквально, как я могу. Давайте посмотрим, как это работает на практике, путем вычисления

nCr(4,2) 
= nCr(4-1, 2-1) + nCr(4-1, 2) 
= nCr(3, 1) + nCr(3, 2) 
= nCr(3-1, 1) + nCr(3-1,0) + nCr(3-1, 2-1) + nCr(3-1, 2) 
= nCr(2, 1) + nCr(2,0) + nCr(2,1) + nCr(2,2) 
= nCr(1, 0) + nCr(1,1) + 1 + nCr(1,0) + nCr(1,1) + 1 
= 1 + 1 + 1 + 1 + 1 + 1 
= 6 

Конечно, мы знали, что уже:

nCr(4,2) = (4 * 3)/(2 * 1) = 6 

Answer 2

рекурсивная функция включает в себя вызовы к себе и случай

терминации в вашем примере nCr = 1 if r = 0 or if r = n образует окончание

и (n-1)C(r-1) + (n-1)Cr - это рекурсия

так что ваш код должен выглядеть somethink так

int nCR(int n, int r){ 
    if (r == 0 || r == n){ 
     return 1; //terminate 
    } 
    else{ 
     return nCr(n-1, r-1) + nCr(n-1, r); //recursive calls 
    } 
}