Recursion vs Iteration

From

Oleg I. Khovayko ()

To

All

Date

2003-01-17T19:04:21Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>

Так!

Моя нетскапа такая-разтакая мало того, что в коре
рухнула - дык еще и послала недоделаное письмо!
Да еще и к тому же как-то криво посылает последующие 
исправления/дополнения, что FIDO-gateway два раза 
отлупы из-за кодировки дает, и не пропускает ничего!!!

Это попытка создать новое письмо, не зависящее от
пред. треда. Пожалуйста, проигнорируйте сегодняшнее
мое письмо от  Fri, 17 Jan 2003 14:48:11 +0000 (UTC).

> считать за труд. Сам же алгоритм простенький, намного короче его и не
> записать:

Итак, Вы признали, что применение рекурсии не дает пользы
дла решения первого примера. И даже написали свое решение,
которое точь-в-точь воспроизводит приведенный мною алгоритм на ML-e.

Хочу отметить еще такой момент: Сначала я дал описание
задачи (что бы подумать), а потом с задержкой привел решение.
Судя по Вашей реакции, вначале Вы не поверили, что матричный
алгоритм и есть решение задачи, и требовали от меня доказательств
адекватности приведенного алгоритма поставлений задаче.

Отсюда вывод: Ваши рекурсивные изыскания в области
разработки алгоритма явно лежали в стороне от правильного
решения. Следовательно, знание рекурсии во всех ее проявлениях
не сильно помогло Вам самому разработать правильный алгоритм
для решения этой задачи. И где-то сутки Вам потребовались,
чтобы убедиться в адекватности приведенного мною матричного 
алгоритма поставленой задаче.

Напоминаю: на topcoder-e люди, не зацикленые исключительно
на рекурсии, такой алгоритм разрабатывают и кодируют примерно 
за 40 минут.
То есть человек получил описание задачи 
(не способа ее решения, а именно описание задачи) - и через 
40 минут засабмитил безглючный код, решающий эту задачу.

----------------------------------------------------------

Перейдем теперь к сравнению примеров:

**** Первый пример:

Итерацинное решение от меня:

 int NumWays(int I, int J, int K, vector< vector<int> > matrix) {
   vector<int> V(N);
   V[I] = 1;
   while(K--)
     V *= matrix; // тут векторное произведение вектора на матрицу
   return V[J];
}

Ваше итерационное решение:

 let numways n i j k m =
   let v0 = Array.make n 0 in v0.(i) <- 1;
   let v = dowhile (fun x -> vm_mul x m) k v0 in
   v.(j)



**** Второй пример:

Мое итерационное решение:

queue<Node*> q;

q.put(&root);

while(!q.empty()) {
 Node *cur = q.front(); q.pop();
 if(cur != NULL) {
   do_something(cur); // Обработаем тек. узел.
   q.push(cur->left); q.push(cur->right); 
 } 
}

Ваше рекурсивное решение:

 let rec tfindl f nl =
   let rec nxtlyr = function
     hd :: tl ->
      (match hd with
        Tnode(v,l,r) -> if f v than raise (Found(v)) else
          l::r::(nxtlyr tl) | Tnone -> nxtlyr tl
       )
    | [] -> []
   in tfindl f (nxtlyr nl)


--------

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

В обшем же случае вопрос стоит так: Сильно ли рекурсия облегчила
жизнь при решении вышеприведенных задач-примеров?

Покамест же я не вижу реальных преимушеств Вашего подхода
перед классическим. 

Резюмирую же я свой ответ фразой из произведения Михаила Афанасьевича Булгакова:

"Вы,  профессор,  воля  ваша, что-то нескладное  придумали!  Оно,
может, и умно, но больно непонятно. Над вами потешаться будут".

-- 
#include <best/regards.hpp>
Oleg I. KHOVAYKO  
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
 * Origin: National Center for Biotechnology Information (2:5020/400)