Факторизация в C-рекурсии

Question

Меня попросили написать функцию void в c(без циклов), которая получает четное число (скажем, 80) и печатает его так: 2*2*5*2*2 Как вы можете видеть, результат равен 80 лол. Между 2 числами нужно напечатать "*", и нечетное число (для моего примера 5) вам нужно напечатать его посередине, или если в числе нечетные числа "2", скажем, 96 нужно напечатать это так:2*2*2*3*2*2 Если заданное число нечетное, верните число. Я хотел бы получить не только ответ, но и то, как вы "думаете" перед тем, как начать писать код. Вот что я получил до сих пор

if(n%4==0)
{
  printf("2*");
  PrintTwos(n/4);
  return;
 }
 if(n%2==0)
 {
 printf("*2");
 PrintTwos(n/2);
  return;
  }
   printf("%d",n);

Answer 1

Вот некоторый псевдокод:

func(nbr)
  isOdd(nbr)         // recursive stop condition
    print nbr
    return

  evenNbr = findFirstEven(nbr)  //return the shortest even number from nbr
  print evenNbr
  func(nbr / evenNbr)

Я не добавил логику для * печать, потому что я уверен, что вы можете понять это самостоятельно. И один случай сломает этот псевдокод, но это хорошее начало, чтобы помочь вам подумать о том, что должна делать ваша рекурсивная функция.

РЕДАКТИРОВАТЬ следующие комментарии: (НЕ ЗАВЕРШЕНО: нечетное число в середине отсутствует в этом)

int findFirstEven(nbr, i) {
    if (nbr%i != 0)
      return findFirstEven(nbr, i++);
    return i;
}

int primefact(int n)
{
    int i=2;
    i = findFirstEven(n, i);

    printf("%d*", i);
    if(n==i)
        printf("1");
        return 0;
    else
        primefact(n/i);
}

(не испытано)

Answer 2

Вам нужно распределить 2 пополам, поэтому перед рекурсивным шагом вам нужно удалить две двойки из числа - в противном случае рекурсивный шаг должен был бы знать, насколько глубоко нужно не печатать слишком много двойок на левой стороне.
Конечно, вы должны проверить, есть ли на самом деле две пары!

Так:

void PrintTwosInNumber(unsigned n)
{
    if(n % 4 == 0)
    {
        printf("2*");
        PrintTwosInNumber(n/4);
        printf("*2");
    }
    else if(n % 2 == 0)
    {
        printf("2*");
        PrintTwosInNumber(n/2);
    }
    else
        printf("%u", n);
}

Вы можете сохранить последний рекурсивный шаг с помощью

void PrintTwosInNumber(unsigned n)
{
    if(n % 4 == 0)
    {
        printf("2*");
        PrintTwosInNumber(n/4);
        printf("*2");
    }
    else if(n % 2 == 0)
        printf("2*%u", n/2);
    else
        printf("%u", n);
}

Редактировать:

Пожалуйста, обратите внимание, что функция попадет в бесконечную рекурсию для n==0 - ноль делится на бесконечно 2, Тем не менее, ноль не может быть представлен как произведение любого числа 2 и некоторого нечетного числа, поэтому он выходит за рамки этой проблемы.
В любом случае, если это была реальная задача программирования, следует принять во внимание этот особый случай и добавить if(n==0) return; ветвь, просто чтобы быть в безопасности, если вызывающая сторона передает неправильное значение параметра.