Потому что думаю, все знают что это такое, а если не знают, то без подсказок не получится, а в подсказки лезть нельзя.

энное число Фибоначчи

Ты серьёзно?

Да как раз есть. Вся фишка FSM лексера именно в том, что он там рекурсивный. тык

Сколько времени у тебя уйдет на обоснование необходимости именно рекурсивной реализации этой функции?

у меня обоснование одно — я туго мыслю, когда дело доходит до рекурсивных реализаций чего-то сложнее, чем обход дерева (это если не лезть в гугл и сделать за минуту-две)

про скорость, стек и прочее, написуя, к примеру, на яве расчет пятого или шестого числа ф. говорить как-то нелепо

я не прошу показывать код, я говорю чисто для себя замерь

Если некомфортно с рекурсией, то плохой программист?

Да. И рекурсии с тобой тоже некомфортно.

полторы минуты

int fib(int n, int a = 0, int b = 1) {
    return n ? fib(n - 1, b, a + b) : a;
}

и ничего кроме рекурсии вам не подойдет

facepalm.jpeg

man «алгоритм поиска в ширину»

man «алгоритм поиска в глубину»

Оба этих алгоритма можно реализовать без рекурсии.

я не прошу показывать код, я говорю чисто для себя замерь

сомнительное удовольствие)

оффтоп, на лоре score как расчитывается? от количества сообщений или от прошедшего времени с момента регистрации?

facepalm.jpeg
man «алгоритм поиска в ширину»
man «алгоритм поиска в глубину»

Та же рекурсия только реализованная вручную.

по идее любой алгоритм можно реализовать без рекурсии раз на то пошло

не путаете ли рекурсивные функции и рекурсивные типы данных?

не путаете ли рекурсивные функции и рекурсивные типы данных?

Нет, любую рекурсивную функцию можно заменить на цикл + ручной стек. Только не всегда нужно.

Не совсем та же...

И нужно, если это не hello world и нет никаких особых соображений, что рекурсия там нужна.

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

Нет, когда некомфортно с рекурсией - это называется Java.

рекурсивной функции, возвращающей энное число Фибоначчи

вон из профессии

да, результат работы этой функции ты будешь ждать намного дольше

Если некомфортно с рекурсией, то либо плохой язык, либо плохой программист, либо плохое кресло.

/thread

ты не волнуйся, он не о статическом дерьме говорит

loop(N) ->

Хоть я и не знаю этого языка (Haskell?) но что-то мне подсказывает, что это таки цикл.

Та же рекурсия только реализованная вручную.

В имплементации это называется «цикл». Хотя алгоритм рекурсивный.

Хоть я и не знаю этого языка (Haskell?) но что-то мне подсказывает, что это таки цикл.

Хоть я тоже не знаю этого языка, капитан мне подскахывает что это рекурсия, там процедура вызывается изнутри самой себя.

там процедура вызывается изнутри самой себя.

Ну, если процедура называется loop, окей. А тогда вопрос: этот их Хаскель что ли адрес возврата для рекурсивных вызовов не запоминает?

Там TCO, если можно развернуть рекурсию в цикл, это делается под ковром. Не для всех случаев, вероятно, но для большинства.

Это Erlang, если что.

Если программисту не комфортно с рекурсией - это значит, что программисту не комфортно с рекурсией. О качестве программиста это ничего не говорит.

Могу полагать, что под комфортностью вы, скорее всего, ощущаете нечто неуловимое под названием «этому тут не место». Рекурсии мало где место. Как и регуляркам, например.

Спасибо. Тогда еще пара вопросов:

1. Что делает тот кусок кода?
2. Он императивен?
3. Там рекурсия или цикл? (Актуально только если ответ на предыдущий вопрос — «да»)

1. Функция хранит состояние.
2. Полностью функционален.
3. Рекурсия с TCO.

Про erlang еще не вспоминали?

1. Функция хранит состояние.

2. Полностью функционален.

Эти вот пунктики не особенно то и сочетаются. Ф-ции с состоянием не вписываются в подстановочную модель, как-бы.

Всё там прекрасно сочетается. Функция инициализуется начальным значением N и ждёт сообщений (аналог блокирующего read). При получении get отсылает процессу P значение N и рекурсивно перезапускает себя (чтоб дальше слушать эфир). При получении set рекурсивно перезапускает себя с N=N2 и таким образом устанавливая новое состояние. При stop тупо завершается. Все эти состояния должны бы храниться на стеке и жрать место, но спасает TCO.

А кто вам сказал, что вы всегда решаете как будут организованы данные? У вас есть на руках конкретный интерфейс к DOM, например, и ничего кроме рекурсии вам не подойдет.

Ты тупой, да? Покажи мне хоть один язык, где невозможно воткнуть самодельный стек. Это даже на Fortran-IV можно, где рекурсией и не пахло.

1. Функция хранит состояние.

Я хотел описания как здесь.

2. Полностью функционален.

Тут я брался утверждать только для императивщины, ибо декларативщина под капотом может иметь что угодно, а в функциональщине не силён.

3. Рекурсия с TCO.

Что по факту более очевидно достигается циклом с аккумулятором (и не заставляет волноваться реализовано ли TCO в ЯП или нет).

Пускай еще обойдёт бинарное (однонаправленное) дерево своей рекурсией с TCO. А вот цикл с кастомным стеком (храним только то, что надо, напр. ссылки/указатели на пройденные узлы) будет куда нагляднее и оптимальнее.

неа.

fix to:

bool хороший_ли_ты_программист() {
    return тебе_комфортно_с_рекурсией 
        || практикуйся_еще()
        || хороший_ли_ты_программист();
    }
}

с просторов интернета:

#include <stdio.h>
 
void multiply(int F[2][2], int M[2][2]);
 
void power(int F[2][2], int n);
 
int fib(int n){
  if (n == 0)
    return 0;
  int F[2][2] = {{1,0},{0,1}};
  power(F, n);
  return F[0][0];
}

int E[2][2] = {{1,1},{1,0}};

void power(int F[2][2], int n){
  if( n == 0)
      return;
  
  if( n > 1){
      power(F, n/2);
      multiply(F, F);
  }
  
  if( n%2 )
     multiply(F, E);
}
 
void multiply(int F[2][2], int M[2][2]){
  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];
 
  F[0][0] = x;
  F[0][1] = y;
  F[1][0] = z;
  F[1][1] = w;
}
 
int main(){
  int n = 9;
  printf("%d", fib(9));
  getchar();
  return 0;
}

если рекурсии некомфортно со мной, то плохая рекурсия?

Состояние стека, не имеет отношения к понятию «функция с сотоянием». Последнее — это функция, которая может возвратить разные значения при одинаковых аргументах.

Неверно.

То о чем ты рассказываешь, к состоянию с точки зрения ФП вообще не имеет отношения, это относится к реализации. В семантике ФП вообще нет состояния. Есть состояние вычислителя, но это уже другой вопрос.

Проблема не в комфортности или некомфортности с рекурсией. И не в проблемах со стеком, и не во вручную реализованном стеке на куче.

Код, как известно, предназначен не только для исполнения машиной,но и для чтения человеком. Читая код, хотелось бы сразу понимать, какую идею хотел выразить программист.

В этом смысле, рекурсивная реализация, когда она естественна(!), как правило более ясна для читателя. И как правило, ее быстрее и проще написать. И если уж возникнут проблемы с производительностью на тестах, то потом можно переписать.

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

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

Ты описал сишника-ембедщика.

Если рекурсия воспринимается как нечто приколоченое сбоку гвоздями, то плохой программист.

Да

/thread

Рекурсивно определение, а рекурсивных вызовов там нет.

type f func() f

func a() f {
  return b
}

func b() f {
  return a
}

func main() {
  for x := a; x != nil; x = x() {
    //
  }
}