Проблема с рекурсивным утверждением

Question

Я пытаюсь понять следующую рекурсивную функцию. Я ожидаю получить возвращаемое значение 3, когда я введу comb3(3,2) для функции.

Вот код python:

def comb3(n, k):
  if (k == 0):
    return 1    
  return comb3(n-1, k-1) * n/k; 

Как я понимаю, здесь разбивка:

comb3(3, 2) = comb3(3-1, 2-1) * 3/2
              comb3(2, 1) * 1

comb3(2, 1) = comb3(2-1, 1-0) * 2/1
comb3(1, 0) * 2

comb3(1, 0) = 1  (k equals to 0, it returns 1)

comb3(2, 1) = 1 * 2 = 2

comb3(3, 2) = 2 * 1 = 2

Проблема в том, что когда я запускаю код, я получаю 3, но я не понимаю, почему.

Answer 1

Ваш лог c неверный, код работает как надо

comb3(3, 2) = comb3(2,1)*3/2
comb3(2, 1) = comb3(1,0)*2/1
comb3(1, 0) = 1

comb3(2, 1) = 1 * 2 / 1 = 2
comb3(3, 2) = 2 * 3 / 2 = 3

Answer 2

Причина, по которой вы получаете 3, заключается в том, что

в вашей первой итерации, проверка if неверна. Таким образом, он переходит к

comb3(n-1, k-1) * n/k;

Эта строка выше разрешит к

comb3(3-1, 2-1) * 3/2;

Следующая итерация также пропустит if проверьте и приведите к

comb3(2-1, 1-1) * 2/1;

На этом этапе оператор if становится истинным, и вы получаете возвращаемое значение 1.

, затем мы умножаем 3/2 * 2/1 * 1 = 3