А не совсем тупое (которое сводиться к tail recursion)? А если вспомнить, что тупое итерационное --- оно тоже тупое (O(n) вместо возможного O(log(n)) на возведении матрицы 2x2 в степень)? А если вспомнить, что есть, вообще говоря, и формула, которое вычисляет его сразу (правда, IRL она не очень применима, по очевидным причинам, но тем не менее)? В общем, правильно --- это давать таки тупое решение, объяснять, почему оно тупое, давать менее тупое, и далее по нарастающей ;-) Закончить можно как раз к концу урока, продемонстрировав заодно опасности чрезмерной оптимизации :-) Если сразу дать нетупое --- нихера не поймут. Если не давать не тупое --- переоценят собственные познания. PS вспоминая книги по программизму, в которых мне попадалось вычисление чисел фибоначи --- там ровно такая последовательность изложения там и была: тупое рекурсивное, "братцы, а что-ж так тормозит, соптимизируем-ка влоб"->рекурсивное с запоминанием, итерационное (в языках с обязательной tail recursion --- соответственно, вариант с ней, родимой). Впрочем, до O(log(n)) доходил мало кто (кажись, у Кнута и у Шеня, или меня склероз подводит?).
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
branchandroot
no subject
Date: 2006-11-16 01:42 am (UTC)А если вспомнить, что тупое итерационное --- оно тоже тупое (O(n) вместо возможного O(log(n)) на возведении матрицы 2x2 в степень)?
А если вспомнить, что есть, вообще говоря, и формула, которое вычисляет его сразу (правда, IRL она не очень применима, по очевидным причинам, но тем не менее)?
В общем, правильно --- это давать таки тупое решение, объяснять, почему оно тупое, давать менее тупое, и далее по нарастающей ;-) Закончить можно как раз к концу урока, продемонстрировав заодно опасности чрезмерной оптимизации :-)
Если сразу дать нетупое --- нихера не поймут. Если не давать не тупое --- переоценят собственные познания.
PS вспоминая книги по программизму, в которых мне попадалось вычисление чисел фибоначи --- там ровно такая последовательность изложения там и была: тупое рекурсивное, "братцы, а что-ж так тормозит, соптимизируем-ка влоб"->рекурсивное с запоминанием, итерационное (в языках с обязательной tail recursion --- соответственно, вариант с ней, родимой). Впрочем, до O(log(n)) доходил мало кто (кажись, у Кнута и у Шеня, или меня склероз подводит?).