Не мог бы кто-нибудь объяснить рекурсию? (не простую как в примерах с факториалом)

@Fibbo · Регистрация: 14.11.2013

Добрый день, вообще я не фанат создавания тем с простыми вопросами, я знаю что такое поиск, но в данном случае я просто не знаю как сформулировать вопрос и что именно искать.

Код на С я потерял, а в разделе питона нет подраздела для новичков, так что напишу на питоне, разницы все равно почти нет:

Python

1 2	def McNuggets(n): return n >= 0 and (n == 0 or n % 6 == 0 or n % 9 == 0 or n % 20 == 0 or McNuggets(n - 6) or McNuggets(n - 9) or McNuggets(n - 20))

Вот какую задачу этот код призван решать:

McDonald’s sells Chicken McNuggets in packages of 6, 9 or 20 McNuggets. Thus, it is possible, for example, to buy exactly 15 McNuggets (with one package of 6 and a second package of 9), but it is not possible to buy exactly 16 McNuggets, since no non- negative integer combination of 6's, 9's and 20's add up to 16. To determine if it is possible to buy exactly n McNuggets, one has to find non-negative integer values of a, b, and c such that

6a + 9b + 20c = n

Write a function, called McNuggets that takes one argument, n, and returns True if it is possible to buy a combination of 6, 9 and 20 pack units such that the total number of McNuggets equals n, and otherwise returns False.

Это задача из курса EDx(может кто знает). Я ее так и не решил, но вообще нашел вот такой вот код. Код работает правильно, с ним проблем нет. Проблема в том что я никак не могу понять как тут работает рекурсия. Может кто-нибудь объяснить пошагово либо дать ссылку куда следует, либо если для таких функций есть какое-то особенное название - дать это название. Спасибо.

На всякий случай:
Как работает

C

1
2
3

int factorial(int x) { 
    return !x ? 1 : x * factorial(x - 1);
}

я понимаю.

@gng · 14.11.2013, 12:20

На Си поленились перевести?

C

int mcn(int n) {
  return (n>=0) && (!(n%6) || !(n%9) || !(n%20)
          || mcn(n-6) || mcn(n-9) || mcn(n-20));
}

И на русский язык тоже?

Смысл простой. Если само число не делится ни на 6, ни на 9, ни на 20, то проверяем это же для чисел n-6, n-9 и n-20. Математика простая. Если аргумент меньше нуля - выход с false.

@Fibbo · 14.11.2013, 15:21 **[ТС]**

Так, вроде бы разобрался. Правильно ли я понимаю происходящее в функции:

mcn(int 35)
!35%6 , 9, 20, поэтому:
mcn(int 35 - 6 = 29)
!29%6 , 9, 20, поэтому:
mcn(int 29 - 6 = 23)
!23%6 , 9, 20, поэтому:
mcn(int 23 - 6 = 17)
!17%6 , 9, 20, поэтому:
mcn(int 17 - 6 = 11)
!11%6 , 9, 20, поэтому:
mcn(int 11 - 6 = 5)
!5%6 , 9, 20, поэтому:
mcn(int 5 - 6 = -1)
Но -1 < 0, так что возвращаемся к предыдущему возвращенному значению и начинаем отнимать 9:
mcn(int 5 - 9 = -4)
Опять отрицательное значение. возвращаемся еще на ступень назад по, так сказать, ветке отнимания шестерки:
mcn(int 11 - 9 = 2)
...

И так пока не придем к ступени когда была отнята только одна шестерка, не отнимем от 29 девятку и не получим число делимое на 20.
Правильно, или это как-то по-другому работает?

Добавлено через 23 минуты
Перевод задачи:

МакДональдс продают Куриные Наггетсы в коробках по 6, 9 и 20 штук. Так что возможно например купить именно 15 наггетсов (1 коробка по 6 штук и 1 по 9), но невозможно купить именно 16, так как нет таких комбинаций чисел 6, 9, и 20 которые в сумме давали бы 16. Для того чтобы узнать можно ли купить n число наггетсов нужно найти положительные целые значения чисел a, b и с при которых

6a + 9b + 20c = n

Напишите функцию, которая принимает один аргумент - n и возвращает True если возможно купить такую комбинацию 6ти, 9ти и 20ти штучных коробок общее число наггетсов в которых равняется n, иначе функция возвращает False

@gng · 14.11.2013, 17:51

Сообщение от Fibbo

И так пока не придем к ступени когда была отнята только одна шестерка, не отнимем от 29 девятку и не получим число делимое на 20.
Правильно, или это как-то по-другому работает?

Правильно.

@Fibbo 0 / 0 / 0 Регистрация: 14.11.2013 Сообщений: 4
	14.11.2013, 15:21 [ТС]	3
	Так, вроде бы разобрался. Правильно ли я понимаю происходящее в функции: mcn(int 35) !35%6 , 9, 20, поэтому: mcn(int 35 - 6 = 29) !29%6 , 9, 20, поэтому: mcn(int 29 - 6 = 23) !23%6 , 9, 20, поэтому: mcn(int 23 - 6 = 17) !17%6 , 9, 20, поэтому: mcn(int 17 - 6 = 11) !11%6 , 9, 20, поэтому: mcn(int 11 - 6 = 5) !5%6 , 9, 20, поэтому: mcn(int 5 - 6 = -1) Но -1 < 0, так что возвращаемся к предыдущему возвращенному значению и начинаем отнимать 9: mcn(int 5 - 9 = -4) Опять отрицательное значение. возвращаемся еще на ступень назад по, так сказать, ветке отнимания шестерки: mcn(int 11 - 9 = 2) ... И так пока не придем к ступени когда была отнята только одна шестерка, не отнимем от 29 девятку и не получим число делимое на 20. Правильно, или это как-то по-другому работает? Добавлено через 23 минуты Перевод задачи: МакДональдс продают Куриные Наггетсы в коробках по 6, 9 и 20 штук. Так что возможно например купить именно 15 наггетсов (1 коробка по 6 штук и 1 по 9), но невозможно купить именно 16, так как нет таких комбинаций чисел 6, 9, и 20 которые в сумме давали бы 16. Для того чтобы узнать можно ли купить n число наггетсов нужно найти положительные целые значения чисел a, b и с при которых 6a + 9b + 20c = n Напишите функцию, которая принимает один аргумент - n и возвращает True если возможно купить такую комбинацию 6ти, 9ти и 20ти штучных коробок общее число наггетсов в которых равняется n, иначе функция возвращает False 0

@gng 918 / 635 / 198 Регистрация: 08.09.2013 Сообщений: 1,690
	14.11.2013, 17:51	4
	Сообщение от Fibbo И так пока не придем к ступени когда была отнята только одна шестерка, не отнимем от 29 девятку и не получим число делимое на 20. Правильно, или это как-то по-другому работает? Правильно. 1

Опции темы