Рекурсия.

[KiberMath]

Здравствуйте.
Очень хочу разобраться с рекурсией. Я понимаю что э то такое (вызов функцией/процедурой самой себя), но как этим пользоваться еще не разобрался. Если кто знает какие-нибудь простенькие задачки на эту тему, пожалуйста дайте ссылку.
Язык желательно Basic или C++
Заранее огромное спасибо

[Xaositect]

Ну, классический пример на рекурсию - это вычисление факториала(возможно, Вы его уже видели).

$$n! = n\cdot (n-1)!$$

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

$$n$$

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

int factorial(int n)
{
   if (n == 0)
      return 1;   //нерекурсивная ветка
   else
      return n*factorial(n-1); //рекурсия
}

Еще рекурсия часто применяется в алгоритмах типа "разделяй и властвуй". Почитайте, например, про Quicksort: http://ru.wikipedia.org/wiki/Быстрая_сортировка

[KiberMath]

C сортировкой я разобрался...
но вот решение задачки о ханойской башне, например, для меня уже тяжеловато... Я совсем запутался =(

[Xaositect]

KiberMath писал(а):

C сортировкой я разобрался...
но вот решение задачки о ханойской башне, например, для меня уже тяжеловато... Я совсем запутался =(

С ханойской башней непонятен алгоритм, или как писать программу?

[KiberMath]

Никак не могу разобраться с самим алгоритмом. Какие действия должна делать та функция которая вызвает сама себя???
... вообще интересно даже не то какие действия должна делать эта функция а как разобраться с тем какие действия должна делать эта функция. Интересен сам ход рассуждений.
С переводом алгоритма на язык программирования проблем никаких нет.

[apatic]

Привет. Вырезал из книжки Либерти для расчета ряда Фибоначчи, может поможет:

int fib(int n);
int main()
{
  int n,answer;
  std::cin >> n;

  answer = fib(n);
....
return 0;
}
  int fib (int n)
  {
  if (n < 3)
    return (1);
  else
    return( fib(n-2) + fib(n-1) );
  }

Извини, что не аккуратно, просто времени мало.

[Андрей АK]

Зачем вообще разбираться с рекурсией?
Это очень вредное явление ... т.е. способ мышления.
Я в своё время ,после того как с ней разобрался ... очень долго отвыкал, в смысле - отвыкал думать рекурсивно - это было трудно, почти как бросить курить ... наверное.

[KiberMath]

Андрей АK
Почему вредное?

[apatic]

KiberMath, видел на википедии код решения ханойской башни рекурсией? Что там не ясно?
Здесь

[KiberMath]

apatic
Так не интересно ))
Я сам хочу придумать алгоритм, а потом сравню

Добавлено спустя 5 минут 29 секунд:

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

Добавлено спустя 11 минут 27 секунд:

Андрей АK
И почему если рекрсия вредна так много олимпиадных задач связанных с рекурсий???

[apatic]

KiberMath, я просто не понял, что тебе нужно? Я думал проблема в том, что ты не понимаешь рекурсии, потом думал, что ты не понимаешь конкретный алгоритм, а теперь узнается, что ты не знаешь алгоритм, а сам его хочешь сочинить. =) В чем нужна помощь? Попробуй до конца понять, что есть рекурсия, посмотри алгоритм, который я для тебя отсканил.
"Рекурсия используется, когда можно выделить самоподобие задачи." © wiki

[KiberMath]

Хм...
А как решить эту задачу без использования рекурсии???

[Йа Гринько]

KiberMath в сообщении #181029 писал(а):

Хм...
А как решить эту задачу без использования рекурсии???

Какую?

[Андрей АK]

KiberMath писал(а):

Андрей АK
Почему вредное?

Во первых, рекурсивные алгоритмы не приспособлены для оптимизации рессурсов.
Мало того что сами они рессурсоёмкие (на каждый вызов процедуры система тратит кучу памяти и скорости), но они не позволяют производить никаких улучшений.
С ростом сложности задачи всё большее количество памяти требуется передавать через стэк - т.е. с увеличением сложности время выполнения возрастает в некой прогрессии.
Кроме того - эту рессурсоёмкость очень трудно оценить - невозможно с первого взгляда догадаться, сколько системе потребуется памяти для такой-то задачи.
Во вторых,
Конечно , зачастую рекурсивный алгоритм выглядит красиво и компактно ... но это может сыграть злую шутку с мозгами и стилем программирования.
Как только вы привыкаете что-то делать при помощи рекурсии, это начинает входить в привычку - даже те задачи, где можно было бы без неё обойтись, вы начинаете решать с помощю рекурсии.
Но если вдруг в вашу логику где-то вкралась ошибка - её иногда трудно обнаружить изучая код рекурсивной программы.
Отладка рекурсивных функций также усложнена.
Рекурсия - она проста и крассива только на небольших и несложных примерах, с увеличением же объёма и сложности она становиться громоздкой и неуклюжей.
А отвыкать уже тяжело - мозги привыкли думать рекурсивно, под конец (когда болезнь совсем запущена) вы уже пытаетесь любой цикл в своей программе заменить рекурсией (циклы уже мозгом не воспринимаются как удачное решение).

Однако, любую рекурсивную программу всегда можно заменить циклом.
Да, приходится использовать массивы считать сколько надо выделить памяти под них ... но ведь чтоб программа хорошо работала всё равно всё это придётся делать.
К тому-же циклы хорошо оптимизируются (в т.ч. рапараллеливаются) , легче отлаживиются, алгоритм предстаёт более явно и наглядно - сразу видны все слабые места и пути оптимизации.

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

[KiberMath]

Йа Гринько писал(а):

KiberMath в сообщении #181029 писал(а):

Хм...
А как решить эту задачу без использования рекурсии???

Какую?

Мда... не уточнил извеняюсь. Я Ханойскую башню имел в виду

Добавлено спустя 1 минуту 27 секунд:

Андрей АK Огромное спасибо за объяснение!
apatic Пасиб большое за скан и за ссылку