Интерестно ваще мнение по Рекурсии

[tro9an]

Только начал изучать рекурсию и не совсем понимаю как она работает, но я чисто для себя вывел типа, "Что такое рекурсия?":
Данное ниже было выведено под "впечатлением" вот этого кода:

Код: [Выделить]

// 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 километр), итак пока не выйдем из туннеля.

Ещё раз скажу, что я это вывел чисто для себя, т.к не очень понимаю как работает рекурсия.
Это нормальное трактование рекурсии, или это бред сивой кобылы?

[Shtsh]

Нет, не нормальная. Смотри — в твоём примере для того, чтобы узнать длину ты просто едешь до конца (хз, зачем мячики). И непонятно, зачем возвращаешься, если длина известна.

Вот задача факториала.
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]

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

[Protopopulus]

Мне пришлось как-то раз переписывать контрольную из-за применения рекурсии -- переполнялся стек. Поэтому, ее целесообразно применять при небольшом числе циклов.

[inkblack]

«Итерация свойственна человеку, рекурсия божественна» — Л. Питер Дойч.

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

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

Или сканирование дерева каталогов.

[Yurror]

Классика рекурсивного жанра не факториал, а обход дерева (дерева каталогов например).
Расчет факториала гораздо понятнее и логичнее описать как итеративный процесс.
Вообще рекурсия довольно жадный до ресурсов процесс, поэтому применять её следует чисто на посмотреть в университете ну и там где совсем без неё никак. а для обхода деревьев есть и итеративные алгоритмы и qsort итеративный тоже есть (он то в основном и используется).

[Marat10.04]

Ещё в пример можно привесит бинарный поиск, в отсортированном массиве.Пусть массив a[ n ];
Искомый элемент сравниваем со серединным элементом массива(a[n/2]), если искомый элемент больше
то ищем его на отрезке [ n/2 +1, n-1 ], иначе на отрезке  [1, n/2 -1 ] и т.д. продолжаем пока не найдем.

[Ururu_2]

понять ,когда нужна рекурсия, а когда нет, просто. Если можешь обойтись циклом или вложенными циклами, не нужна тебе рекурсия. Если же нужно много вложенных циклов, да ещё и неясно, сколько именно - делай рекурсию.