Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 36
Чтобы понять рекурсию, надо сперва понять рекурсию. (ц)
Поправьте факториал, дабы не вводить никого в заблуждение:
0! = 1;
N! = N * (N-1)!
0! = 1;
N! = N * (N-1)!
Итерация от человека. Рекурсия — от Бога. — Л. Питер Дойч
А вообще то, что на хабре в последнее время детский сад разводят меня как-то удручает.
А вообще то, что на хабре в последнее время детский сад разводят меня как-то удручает.
Теперь по делу:
вы упрекаете версию K&R в неэффективности в то время как предложенная рекурсивная реализация мало того что выделяет динамическую память, засоряет стек и мешает рекурсию с мутабельным состоянием, так еще и не отличается ясностью.
>*(mas+szmem) = (char) 0;
mas[szmem] = (char) 0; — для слабых духом?
вы упрекаете версию K&R в неэффективности в то время как предложенная рекурсивная реализация мало того что выделяет динамическую память, засоряет стек и мешает рекурсию с мутабельным состоянием, так еще и не отличается ясностью.
>*(mas+szmem) = (char) 0;
mas[szmem] = (char) 0; — для слабых духом?
> переворачивать каждый строчку после преобразования — не комильфо. Потому как подобные вызовы весьма часты и это, несомненно, скажется на производительности.
поверьте рекурсия куда более прожорлива чем вызов одной единственной фукнции
поверьте рекурсия куда более прожорлива чем вызов одной единственной фукнции
Выделяет динамическую память по причине неизвестности того, сколько её нужно выделить.
Скорее всего тут имеет место просто несчастный случай.
«Засоряет стек» — это свойство любой рекурсии.
Это самое «мутабельное состояние» в хороших языках делают с помощью необязательных параметров.
На счёт ясности — да надо малость перекомпоновать блоки. Ну и ещё комментарии делают код не очень читаемым. Сам думал, как лучше — после откомментировать или в самом коде. Решил что лучше в коде. Теперь уже не знаю ;)
А последнее — ну раз с указателями начал мутить, так придерживаюсь одного стиля :)
Скорее всего тут имеет место просто несчастный случай.
«Засоряет стек» — это свойство любой рекурсии.
Это самое «мутабельное состояние» в хороших языках делают с помощью необязательных параметров.
На счёт ясности — да надо малость перекомпоновать блоки. Ну и ещё комментарии делают код не очень читаемым. Сам думал, как лучше — после откомментировать или в самом коде. Решил что лучше в коде. Теперь уже не знаю ;)
А последнее — ну раз с указателями начал мутить, так придерживаюсь одного стиля :)
Вообще такие примеры использования рекурсии как раз и приводят к неверному ее пониманию другими. Все, что можно просто реализовать через циклы, должно быть реализовано через циклы. Оставьте рекурсии задачи обхода дерева или синтаксического анализа, а факториал — через for (int i = 1; i <= n; i++) {}
имхо слишком сложный код чтобы обучить кого-то рекурсии.
еще за счет статических функций у вас получилась фукнция которую нельзя вызывать из разных потоков ( то есть не reentrant ) что имхо гораздо хуже чем вариант K&R с передачей указателя на массив.
еще за счет статических функций у вас получилась фукнция которую нельзя вызывать из разных потоков ( то есть не reentrant ) что имхо гораздо хуже чем вариант K&R с передачей указателя на массив.
свят, свят, свят.
у меня такой вопрос: зачем вы пишите на Си, если вы не умеете писать на Си? зачем вы пытаетесь обучать других, если сами только учитесь?
знаете почему функции часто принимают указатели на буфферы, а не выделяют их сами? потому что так пользователь кода получает полный контроль на способом выделения и временем жизни буфера, например, он может разместить его на стэке. для 32битного знакового числа нам нужно все 10 байт — глупо в общем случае лезть за 10 байтами в кучу.
а что за восхитительные подход к обработке ошибок выделения памяти!
а этот прекрасный идентификатор mas происходящий от чудесного английского слова massiv.
а эти статические локальные переменные!
а эти нестатические локальные массивы!
а эти чудесные дефайны! о боже, кто вас научил столь изящному способу объявлять константы? я уж думал он потерян в веках со времен поддержки enum в С компиляторах… но нет еще остались хранители древнего знания…
уф…
у меня такой вопрос: зачем вы пишите на Си, если вы не умеете писать на Си? зачем вы пытаетесь обучать других, если сами только учитесь?
знаете почему функции часто принимают указатели на буфферы, а не выделяют их сами? потому что так пользователь кода получает полный контроль на способом выделения и временем жизни буфера, например, он может разместить его на стэке. для 32битного знакового числа нам нужно все 10 байт — глупо в общем случае лезть за 10 байтами в кучу.
а что за восхитительные подход к обработке ошибок выделения памяти!
а этот прекрасный идентификатор mas происходящий от чудесного английского слова massiv.
а эти статические локальные переменные!
а эти нестатические локальные массивы!
а эти чудесные дефайны! о боже, кто вас научил столь изящному способу объявлять константы? я уж думал он потерян в веках со времен поддержки enum в С компиляторах… но нет еще остались хранители древнего знания…
уф…
Я тоже только учусь, не могли бы вы обьяснить как будет правильно в тех местах которые указали?
правильным будет выкинуть написанную функцию на помойку и когда понадобится перевести число в строку пользоваться чем-нибудь стандартным.
по отдельным пунктам:
0) принимать указатель на буфер это хорошо. если при этом еще заботится о проверке на достаточность размера буфера, то это еще лучше.
1) assert(xxx) срабатывает только в отладочной версии, в релизной версии assert ничего не делает. соответственно если у нас случилась ошибка выделения памяти, то это мы не поймаем и можем получить неприятные последствия (в данном конкретном случае запись памяти по адресу 0+что-то маленькое. скорее всего при первой же попытки записать мы отвалимся с segfault, но это не кошерно).
2) если уж пишете программы имейте привычку называть переменные нормальными английскими именами, а не транслитирированными рускими словами massiv или там perestanovka.
3) просто не надо использовать статические локальные переменные где попало. это как уже замечено делает функции не реетрабельными и вызывает страшные головные боли связанные с их инициализацией в многопоточной среде… случаев из практики, когда они действительно были бы полезны я могу пересчитать по пальцам левой руки. здесь они не по делу
4) непонятно зачем в функции объявлены два локальных массива (даже не статических), которые по логике вещей можно было бы сделать глобальными. они просто замусоривают стэк.
5) для создания таких констант нужно использовать enum:
перечисления в Си, конечно, не столь типобезопасны как в языках типа Modula-2, но все же лучше чем лешие старообрядческие дефайны.
по отдельным пунктам:
0) принимать указатель на буфер это хорошо. если при этом еще заботится о проверке на достаточность размера буфера, то это еще лучше.
1) assert(xxx) срабатывает только в отладочной версии, в релизной версии assert ничего не делает. соответственно если у нас случилась ошибка выделения памяти, то это мы не поймаем и можем получить неприятные последствия (в данном конкретном случае запись памяти по адресу 0+что-то маленькое. скорее всего при первой же попытки записать мы отвалимся с segfault, но это не кошерно).
2) если уж пишете программы имейте привычку называть переменные нормальными английскими именами, а не транслитирированными рускими словами massiv или там perestanovka.
3) просто не надо использовать статические локальные переменные где попало. это как уже замечено делает функции не реетрабельными и вызывает страшные головные боли связанные с их инициализацией в многопоточной среде… случаев из практики, когда они действительно были бы полезны я могу пересчитать по пальцам левой руки. здесь они не по делу
4) непонятно зачем в функции объявлены два локальных массива (даже не статических), которые по логике вещей можно было бы сделать глобальными. они просто замусоривают стэк.
5) для создания таких констант нужно использовать enum:
typedef enum {
DEC = 0, OCT = 1, HEX = 2, BIN = 3
} Base;
перечисления в Си, конечно, не столь типобезопасны как в языках типа Modula-2, но все же лучше чем лешие старообрядческие дефайны.
На С я когда-то давно писал. И уже практически забыл его, потому как задач под него совсем не было.
Данный пост — просто небольшое исследование, идея, если хотите. Я не декларировал его как 100% продакшн. Это ПРИМЕР.
Я прекрасно знаю, почему функции получают указатели на буферы. Здесь просто прорабатывался вопрос о том, что будет, если _есть некие данные, кои надо разместить в памяти, но пока размер их не известен_. Просто как часть проблемы.
«Восхительный подход к обработке ошибок выделения памяти» — для скорости и краткости чтобы не городить огород в коде.
«Прекрасный идентификатор mas» — не придирайтесь к буквам, уважаемый. Я прекрасно знаю, что массив по английски — array. И много других страшных слов также мне известны.
В вашем комментарии — сплошной выпендрёж. Этот пост НЕ О ПРОГРАММИРОВАНИИ НА С.
И, боюсь, что рабочего кода в этой жизни вы гораздо меньше меня написали.
И на всякий случай, раз вы такой понятливый. Я не призываю повсеместно использовать рекурсию.
Данный пост — просто небольшое исследование, идея, если хотите. Я не декларировал его как 100% продакшн. Это ПРИМЕР.
Я прекрасно знаю, почему функции получают указатели на буферы. Здесь просто прорабатывался вопрос о том, что будет, если _есть некие данные, кои надо разместить в памяти, но пока размер их не известен_. Просто как часть проблемы.
«Восхительный подход к обработке ошибок выделения памяти» — для скорости и краткости чтобы не городить огород в коде.
«Прекрасный идентификатор mas» — не придирайтесь к буквам, уважаемый. Я прекрасно знаю, что массив по английски — array. И много других страшных слов также мне известны.
В вашем комментарии — сплошной выпендрёж. Этот пост НЕ О ПРОГРАММИРОВАНИИ НА С.
И, боюсь, что рабочего кода в этой жизни вы гораздо меньше меня написали.
И на всякий случай, раз вы такой понятливый. Я не призываю повсеместно использовать рекурсию.
Проблема примеров в том что они должны быть идеальны во всем что не касается предмета обсуждения. Иначе будет как всегда и как тут — куча замечаний не по теме.
Но это не означает что они не по делу :)
Но это не означает что они не по делу :)
Пример на языке на котором вы не пишите? Зачем? Давайте я коверкая слова буду пытаться вести здесь диалог на японском… Это будет выглядеть очень странно.
Дело не в том продакш или не продакш. Дело в том, что вы иллюстрируете свои мысли плохим неаккуратным кодом. Ничего хорошего в этом нет, хотя бы потому что на здесь есть люди, которые никогда не писали на Си и они могут из ващего кода подчерпнуть много неприятного.
>> Здесь просто прорабатывался вопрос о том, что будет, если _есть некие данные, кои надо разместить в памяти, но пока размер их не известен_.
Ох оставьте это! Никакой вопрос здесь не «прорабатывался». Я не вижу анализа этой проблемы (которая я сомневаюсь что и вообще может быть решена красиво в общем случае). Иллюстрирующий пример высосан из пальца и имеет плохой дизайн с моей точки зрения.
>> И много других страшных слов также мне известны.
Так используйте их.
>> И, боюсь, что рабочего кода в этой жизни вы гораздо меньше меня написали.
Вполне возможно. Но сколько бы вы не написали кода в жизни это не дает вам права выкладывать на всеобщее обозрения такой код, который вы написали выше. Заслуги перед отечеством здесь простите значения не имеют.
>> Этот пост НЕ О ПРОГРАММИРОВАНИИ НА С.
Я заметил. Еще раз: не используйте язык на котором вы не говорите для иллюстрации своих мыслей. Иначе получается странно.
>> Я не призываю повсеместно использовать рекурсию.
И что? Этот вопрос лежит вне плоскости нашей беседы.
Дело не в том продакш или не продакш. Дело в том, что вы иллюстрируете свои мысли плохим неаккуратным кодом. Ничего хорошего в этом нет, хотя бы потому что на здесь есть люди, которые никогда не писали на Си и они могут из ващего кода подчерпнуть много неприятного.
>> Здесь просто прорабатывался вопрос о том, что будет, если _есть некие данные, кои надо разместить в памяти, но пока размер их не известен_.
Ох оставьте это! Никакой вопрос здесь не «прорабатывался». Я не вижу анализа этой проблемы (которая я сомневаюсь что и вообще может быть решена красиво в общем случае). Иллюстрирующий пример высосан из пальца и имеет плохой дизайн с моей точки зрения.
>> И много других страшных слов также мне известны.
Так используйте их.
>> И, боюсь, что рабочего кода в этой жизни вы гораздо меньше меня написали.
Вполне возможно. Но сколько бы вы не написали кода в жизни это не дает вам права выкладывать на всеобщее обозрения такой код, который вы написали выше. Заслуги перед отечеством здесь простите значения не имеют.
>> Этот пост НЕ О ПРОГРАММИРОВАНИИ НА С.
Я заметил. Еще раз: не используйте язык на котором вы не говорите для иллюстрации своих мыслей. Иначе получается странно.
>> Я не призываю повсеместно использовать рекурсию.
И что? Этот вопрос лежит вне плоскости нашей беседы.
Проблема из пальца не высосана, я об этом внятно написал в посте.
Так на всякий случай:
А вы когда-нить читали ядро Линукса. Ну любопытства ради хотя б?
Ну или исходники понравившейся библиотеки дабы почерпнуть, так сказать?
Там всё сильно отличается от того, как учили. Полно сюрпризов. Да и приличный код получается не сразу. После пересмотра и вылизывания его.
Видимо, пост придётся проапдейтить, а то тут меня съедят.
Так на всякий случай:
А вы когда-нить читали ядро Линукса. Ну любопытства ради хотя б?
Ну или исходники понравившейся библиотеки дабы почерпнуть, так сказать?
Там всё сильно отличается от того, как учили. Полно сюрпризов. Да и приличный код получается не сразу. После пересмотра и вылизывания его.
Видимо, пост придётся проапдейтить, а то тут меня съедят.
>> А вы когда-нить читали ядро Линукса.
А то! И ядро QNX даже читал… И даже первую страницу книги Льва Николаевича Толстого «Война и Мир».
Только все это не имеет отношение к делу.
Во-первых, код библиотек как бы он не был написан является исключительно проблемой авторов. Если у меня есть претензии к стилю — я их не вам буду высказывать. Кстати, в ядре Линукс нормально так пишут. Многие места вообще до блеска вылизаны за все это время…
Во-вторых, если кто-то пишет плохой код это не значит, что вы должны писать плохой код и выкладывать его на всеобщее обозрение не пересмотрев и не вылизав. У вас сроки не горят и заказчик не буйствует…
В-третьих, кто вам сказал, что меня «учили»? Мои культура написания на Си проистекает как раз из практики, различных корпоративных стандартов, чтения чужого кода и чувства прекрасного, которое должно быть у каждого программиста.
А то! И ядро QNX даже читал… И даже первую страницу книги Льва Николаевича Толстого «Война и Мир».
Только все это не имеет отношение к делу.
Во-первых, код библиотек как бы он не был написан является исключительно проблемой авторов. Если у меня есть претензии к стилю — я их не вам буду высказывать. Кстати, в ядре Линукс нормально так пишут. Многие места вообще до блеска вылизаны за все это время…
Во-вторых, если кто-то пишет плохой код это не значит, что вы должны писать плохой код и выкладывать его на всеобщее обозрение не пересмотрев и не вылизав. У вас сроки не горят и заказчик не буйствует…
В-третьих, кто вам сказал, что меня «учили»? Мои культура написания на Си проистекает как раз из практики, различных корпоративных стандартов, чтения чужого кода и чувства прекрасного, которое должно быть у каждого программиста.
>> Проблема из пальца не высосана, я об этом внятно написал в посте.
Проблема неизвестных размеров из пальца не высосана, согласен и возникает достаточно часто. Но я говорил нечто другое: иллюстрирующий её пример высосан из пальца, я все-таки считаю что в данном конкретном случае передавать указатель на буфер (размер которого как я уже говорил не превосходит 10 байт) было бы более красиво и правильно.
Проблема неизвестных размеров из пальца не высосана, согласен и возникает достаточно часто. Но я говорил нечто другое: иллюстрирующий её пример высосан из пальца, я все-таки считаю что в данном конкретном случае передавать указатель на буфер (размер которого как я уже говорил не превосходит 10 байт) было бы более красиво и правильно.
Рекурсия в общем случае это весьма страшное зло для компьютера: банально стек забивается, оптимизировать её тяжело. Если задачу можно эффективно выполнить без рекурсии, то нужно её именно так выполнять и никак иначе.
(есть конечно хвостовая рекурсия, которая хорошо оптимизируется и вообще разворачивается в циклы, но это лишь частный случай)
(есть конечно хвостовая рекурсия, которая хорошо оптимизируется и вообще разворачивается в циклы, но это лишь частный случай)
Я понимаю, что рекурсия — это из такой розовой математической мечты ;) Я и не призываю её использовать повсюду. Особенно на С. Тут выше уже сказали, что она хорошо годится для обхода деревьев и синтаксического анализа.
Вот, если бы вы написали «Реализация рекурсивных функций для многопоточной обработки»… А то так, как здесь
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
О рекурсивных процедурах