Форум русскоязычного сообщества Ubuntu


Хотите сделать посильный вклад в развитие Ubuntu и русскоязычного сообщества?
Помогите нам с документацией!

Автор Тема: Интерестно ваще мнение по Рекурсии  (Прочитано 766 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн tro9an

  • Автор темы
  • Любитель
  • *
  • Сообщений: 55
    • Просмотр профиля
Интерестно ваще мнение по Рекурсии
« : 07 Февраля 2011, 00:24:05 »
Только начал изучать рекурсию и не совсем понимаю как она работает, но я чисто для себя вывел типа, "Что такое рекурсия?":
Данное ниже было выведено под "впечатлением" вот этого кода:
// factor2.cpp

// подсчет факториала числа с помощью рекурсии

#include <iostream>

using namespace std;

unsigned long factfunc(unsigned long); // прототип

int main()

{

  int n;                               // число, вводимое пользователем

  unsigned long fact;                  // факториал этого числа

  cout << "Введите целое число :";

  cin >> n;

  fact = factfunc(n);

  cout << "Факториал числа " << n << " равен " << fact << endl;

  return 0;

}

//--------------------------------------------------------

// функция factfunc()

// рекурсивно подсчитывает факториал числа

unsigned long factfunc(unsigned long n)

{

  if(n > 1)

    return n * factfunc(n-1);          // вызов самой себя

  else

    return 1;

}




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

Представим что у нас есть туннель и машина, и мы хотим узнать длину тоннеля, будим двигаться по туннелю пока не упрёмся в стену (т.е пока условие верно).
На протяжении всего пути, через каждый километр, будим выкидывать что-нибудь (без разницы что, например красный футбольный мяч).
Итак мы упёрлись в стену (т.е условия неверно), быстренько разворачиваемся, и едем обратно, подбирая по пути мячики (один мяч +1 километр), итак пока не выйдем из туннеля.

Ещё раз скажу, что я это вывел чисто для себя, т.к не очень понимаю как работает рекурсия.
Это нормальное трактование рекурсии, или это бред сивой кобылы?
« Последнее редактирование: 07 Февраля 2011, 01:35:56 от tro9an »

Оффлайн Shtsh

  • Участник
  • *
  • Сообщений: 118
    • Просмотр профиля
Re: Интерестно ваще мнение по Рекурсии
« Ответ #1 : 07 Февраля 2011, 02:36:50 »
Нет, не нормальная. Смотри — в твоём примере для того, чтобы узнать длину ты просто едешь до конца (хз, зачем мячики). И непонятно, зачем возвращаешься, если длина известна.

Вот задача факториала.
fact(2)=1*2
fact(3)=1*2*3=fact(2)*3
fact(4)=1*2*3*4=fact(3)*4

Соответственно fact(n)=fact(n-1)*n, что очень легко записывается рекурсивно.
Нужно только проверять, не стало ли n-1=1.

И да, в программе ошибка - она не посчитает факториал от 0.

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

Оффлайн hippi90

  • Активист
  • *
  • Сообщений: 433
    • Просмотр профиля
Re: Интерестно ваще мнение по Рекурсии
« Ответ #2 : 07 Февраля 2011, 02:49:31 »
Рекурсия - палка о двух концах, с применением рекурсии записать алгоритм можно быстрее и короче, с другой стороны, ухудшается читаемость кода, для рекурсии специфичны ошибки типа переполнения стека.

Оффлайн Protopopulus

  • Старожил
  • *
  • Сообщений: 1690
  • А чего вы так смотрите?..
    • Просмотр профиля
Re: Интерестно ваще мнение по Рекурсии
« Ответ #3 : 07 Февраля 2011, 02:57:54 »
Мне пришлось как-то раз переписывать контрольную из-за применения рекурсии -- переполнялся стек. Поэтому, ее целесообразно применять при небольшом числе циклов.
Если ты владеешь знаниями, то и знания владеют тобой. (с) Protopopulus

Оффлайн inkblack

  • Старожил
  • *
  • Сообщений: 1216
    • Просмотр профиля
Интерестно ваще
« Ответ #4 : 07 Февраля 2011, 03:03:17 »
«Итерация свойственна человеку, рекурсия божественна» — Л. Питер Дойч.

С факториалом не так интересно и не очень понятно, зачем надо делать именно так. Ведь можно обойтись простым циклом.

А посмотрите лучше пример программы qsort у Кернигана и Ритчи — очень даже по делу рекурсия.

Или сканирование дерева каталогов.
Делюсь знаниями, но их у меня мало!

Оффлайн Yurror

  • Старожил
  • *
  • Сообщений: 1966
    • Просмотр профиля
Re: Интерестно ваще мнение по Рекурсии
« Ответ #5 : 07 Февраля 2011, 06:06:30 »
Классика рекурсивного жанра не факториал, а обход дерева (дерева каталогов например).
Расчет факториала гораздо понятнее и логичнее описать как итеративный процесс.
Вообще рекурсия довольно жадный до ресурсов процесс, поэтому применять её следует чисто на посмотреть в университете ну и там где совсем без неё никак. а для обхода деревьев есть и итеративные алгоритмы и qsort итеративный тоже есть (он то в основном и используется).

Оффлайн Marat10.04

  • Новичок
  • *
  • Сообщений: 13
    • Просмотр профиля
Re: Интерестно ваще мнение по Рекурсии
« Ответ #6 : 07 Февраля 2011, 18:11:24 »
Ещё в пример можно привесит бинарный поиск, в отсортированном массиве.Пусть массив a[ n ];
Искомый элемент сравниваем со серединным элементом массива(a[n/2]), если искомый элемент больше
то ищем его на отрезке [ n/2 +1, n-1 ], иначе на отрезке  [1, n/2 -1 ] и т.д. продолжаем пока не найдем.

Оффлайн Ururu_2

  • Активист
  • *
  • Сообщений: 291
    • Просмотр профиля
Re: Интерестно ваще мнение по Рекурсии
« Ответ #7 : 08 Февраля 2011, 19:06:37 »
понять ,когда нужна рекурсия, а когда нет, просто. Если можешь обойтись циклом или вложенными циклами, не нужна тебе рекурсия. Если же нужно много вложенных циклов, да ещё и неясно, сколько именно - делай рекурсию.

 

Страница сгенерирована за 0.042 секунд. Запросов: 25.