рекурсивная функция

[AngelMarik]

Доброго времени суток!

Делаю лабораторку, задание звучит так:
"Написать программу, использующую рекурсивную функцию для определения, является ли число "почти совершенным". "Почти совершенное" число – это число из ряда натуральных чисел, которое равно сумме своих делителей, не обязательно всех (исключая само число)"

Почти совершенное число, например 12: его делители - 1 2 3 4 6
12=6+3+2+1
12=6+4+2
и т.д

подскажите, пожалуйста как эту задачку решить?

я так понимаю нужно перебором искать суммы делителей числа, а вот как это сделать чет пока не понимаю

на с++ делаю

[Abstraction]

Что-то до меня категорически не доходит, где здесь органично вписывается рекурсия.
Нет, вписать-то можно, но обоснование будет для начинающего, самое малое, зубодробительным.
1) Пусть критерий принадлежности числа к почти совершенным - P(n). То есть, P(12) - "верно", P(17) - "неверно".
2) Введём вспомогательное множество троек, заданное критерием Q(n, s, m), соответствующее "s - сумма некоторых делителей n, каждый из которых не меньше m и s можно дополнить некоторыми делителями n меньшими m до суммы, равной n". Перечитайте это ещё раз. То есть, Q(12, 6, 5) - "верно" (к 6 можно добавить делители 12 3, 2 и 1 и в сумме получится 12), а Q(12, 6, 3) - "неверно" (меньше 3 только делители 2 и 1, если прибавить их к 6, 12 мы не получим).
3) Если P(n), то Q(n, 0, n-1) и наоборот. Подумайте, почему.
4) Q(n, n, x) - "верно"; Q(n, y, 1), при y<n -"неверно", Q(n, y, x) при y>n - "неверно".
5) Q(n, s, m) "верно" если и только если Q(n, s, m-1) либо {(n делится на m-1) и Q(n, s+m-1, m-1)}. (Q(n, s, m) верно - значит, к s можно добавить какие-то делители меньше m так чтобы получить n; этот набор либо включает m-1, либо не включает.)
6) А теперь - код (по сути - прямой перенос наших пунктов 3), 4) и 5)):

bool Q(int n, int s, int m){
  if(s == n) return true; //4)
  if(s > n) return false;
  if(m == 1) return false;

  if(Q(n, s, m-1)) return true; //5)
  if(n % (m-1) != 0) return false;
  return Q(n, s+m-1, m-1);
}

bool P(int n){
  return Q(n, 0, n-1); //3)
}