1. C# / Говнокод #18722

    +1

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    class Program
{
        static void Main()
        {
            UInt64 num;
            Console.WriteLine(num = F(Convert.ToUInt64(Console.ReadLine())));
            Main();
        }

        static UInt64 F(UInt64 number)
        {
            return number <= 0 ? 1 : number * F(number - 1);
        }
}

    Считывание числа и выдача его факториала while(true).

    Запостил: alexey_70707, 15 Сентября 2015

    Комментарии (34) RSS

    • ava guest 15.09.2015 13:29 # 0

      и хде тут говнокод ткни пальцем в упор невижу
      Ответить

      • ava 3_14dar 15.09.2015 15:46 # 0

        Наверно это
        UInt64 num;
        Console.WriteLine(num = F(Convert.ToUInt64(Console.ReadLine()))) ;

        Эклипс уже бы матюкнулся наверно
        Ответить

        • ava guest 15.09.2015 15:57 # +1

          в C# присваивание как и в С возвращает значение
          F() вызов рекурсивной функции всё остальное тоже нормально
          Ответить

      • ava guest 15.09.2015 16:02 # +1

        Всё нашел. Пока не посмотрел под отладчиком не заметил рекурсивный вызов Main() в 7 строке
        Ответить

        • ava 3_14dar 15.09.2015 16:05 # 0

          Факториал же.
          Ответить

          • ava guest 15.09.2015 16:23 # 0

            Факториал это рекурсивный вызов F()
            а рекурсивный вызов Main() это говнокод с переполнением стэка от бесконечной рекурсии
            Ответить

            • ava 3_14dar 15.09.2015 16:57 # +1

              Точон
              Ответить

            • ava Her 16.09.2015 00:30 # 0

              Console.ReadLine вызывает прерывание ОС, которое позволит выйти из рекурсии для Main() в нужный момент
              Ответить

              • ava bormand 16.09.2015 05:59 # 0

                Да просто исключение кинет, когда числа кончатся.

                Кстати, а шарп хвостовую рекурсию оптимизирует?
                Ответить

                • ava 3_14dar 16.09.2015 07:57 # 0

                  Нахуя? Нахуя это в императивных языках?
                  Ответить

                  • ava roman-kashitsyn 16.09.2015 11:08 # 0

                    > в императивных языках
                    Иногда алгоритмы ощутимо проще выразить (и корректно написать с первого раза) хвостовой рекурсией, чем циклом.
                    static long sum(Iterator<Long> i, long acc) {
    return i.hasNext() ? sum(i, i.next() + acc) : acc;
}
                    vs
                    static long sum(Iterator<Long> i, long acc) {
    while (i.hasNext()) {
        acc += i.next();
    }
    return acc;
}
                    Ответить

                    • ava 3_14dar 16.09.2015 14:32 # +1

                      Мне второе вполне понятно.
                      Ответить

                      • ava roman-kashitsyn 16.09.2015 15:07 # 0

                        Оно и должно быть понятно, это тривиальный алгоритм, но даже в нём рекурсивная версия компактней и лучше отражает намерения "добавляем число к сумме и складываем оставшиеся".
                        На более сложных примерах профит может быть более заметным. Быстрое возведение в степень:
                        // Require: n >= 1
public static long pow1(long a, long b, int n) {
  while (n > 1) {
    if (n % 2 != 0) {
      a *= b;
      n -= 1;
    } else {
      b *= b;
      n /= 2;
    }
  }
  return a * b;
}
public static long pow(long a, long b, long n) {
  if (n <= 1)     return a * b;
  if (n % 2 != 0) return pow(a * b, b,     n - 1);
  else            return pow(a,     b * b, n / 2);
}
                        В какой версии проще проверить, что a * b ^ n == const?
                        Ответить

                        • ava 3_14dar 16.09.2015 15:20 # 0

                          Если и есть, разница не такая большая чтобы изъябываться с оптимизацией хвостовой рекурсии.
                          Ответить

                        • ava guest 18.09.2015 12:47 # +1

                          конечно в первой потому-что при
                          pow(1, 1, Int64.MaxValue)
                          тебе стек распидорасит, а с циклом он хотя-бы не упадёт и вообще
                          // Require: n >= 1
public static long pow1(long a, long b, int n) {
  while (n > 1) {
    if (n & 1 != 0) {
      a *= b; n--;
    } else {
      b *= b; n >>= 1;
    }
  }
  return a * b;
}

                          деление тут не нужно
                          Ответить

                          • ava 3_14dar 18.09.2015 12:51 # 0

                            Гость, worst case за 2*количество битов в степени операций.
                            Ответить

                          • ava TarasB 18.09.2015 12:52 # 0

                            нет тут деления и не было
                            Ответить

                          • ava roman-kashitsyn 18.09.2015 12:53 # +3

                            > деление тут не нужно

                            Я вставил деление, чтобы пидар на умножение/деление сдвигами снова не вонял.

                            > тебе стек распидорасит, а с циклом он хотя-бы не упадёт

                            Опять умник появился? тред не читай @ комментируй очевидное
                            Ты обсуждение про tail call recursion optimization читал?

                            Ну и глубина рекурсии даже в твоём случае не будет больше 64. Алгоритм логарифмический.
                            Ответить

                            • ava 3_14dar 18.09.2015 12:54 # −2

                              Руснявенький, во-первых, воняешь здесь ты, во-вторых, я умножение сдвигами упоминал в немного другом контексте
                              Ответить

                        • ava TarasB 18.09.2015 14:02 # 0

                          Проще так:
                          public static long pow(long a, long n) {
  if (n<=0) return 1;
  if (n == 1)     return a;
  if (n % 2 != 0) return a*pow(a,n-1);
  else            return sqr(pow(a,n/2));
}

                          Переменная-накопитель нужна лишь для нерекурсии.
                          Ответить

                          • ava roman-kashitsyn 18.09.2015 14:06 # +1

                            > Переменная-накопитель нужна лишь для нерекурсии

                            Я умышленно написал так, чтобы вменяемый компилятор мог применить tail call recursion optimization и превратить рекурсивный код в цикл.
                            Ответить

                • ava roman-kashitsyn 16.09.2015 11:01 # 0

                  > шарп хвостовую рекурсию оптимизирует?
                  На SO говорят, что нет
                  http://stackoverflow.com/questions/491376/why-doesnt-net-c-optimize-for-tail-call-recursion
                  Ответить

                  • ava guest 18.09.2015 12:31 # 0

                    МС так на фа-диез пытается народ подсадить
                    ну а хули? программисту же, кроме как иль мерджить, делать нехуй
                    Ответить

    • ava imihajlov 15.09.2015 15:14 # +2

      Это функциональный стиль! Зачем нам циклы, если есть рекурсия!
      Ответить

      • ava roman-kashitsyn 15.09.2015 15:30 # +1

        Функциональщики либо пишут c хвостовой рекурсией, либо 
        Enumerable.Range(1, number).Aggregate(1, (x, y) => x * y)
        Ответить

        • ava imihajlov 15.09.2015 15:31 # +1

          Это говнокод, тут каждый пишет как ему вздумается.
          Ответить

          • ava roman-kashitsyn 16.09.2015 11:13 # +1

            Более того - люди пишут как им вздумается не только на ГК.
            Ответить

        • ava stasmarkin 21.09.2015 09:24 # 0

          А второй вариант плох?
          Ответить

          • ava roman-kashitsyn 21.09.2015 11:01 # 0

            Второй это который?
            Ответить

            • ava stasmarkin 21.09.2015 11:20 # 0

              Enumerable.Range(1, number).Aggregate(1, (x, y) => x * y)
              Ответить

              • ava roman-kashitsyn 21.09.2015 11:28 # 0

                а кто-то утверждал, что он плох?
                Ответить

                • ava stasmarkin 21.09.2015 12:01 # −1

                  из контекста и строения фразы показалось, что вы противопоставляете метод с Enumerable хвостовой рекурсией.
                  Типа, функциональщики пушит (нормально) с хвостовой рекурсией или (через жопу) с Enumerable
                  Ответить

                  • ava roman-kashitsyn 21.09.2015 12:10 # 0

                    Это только ваши домыслы, я ничего такого не подразумевал. Оба варианта вполне приемлимы. Вариант с хвостовой рекурсией в теории лучше поддаётся оптимизациям компилятора, но это далеко не всегда приносит какой-то профит.
                    Ответить

    Добавить комментарий