Избавление от рекурсии
От: MikaRSDN Soukhov Stock#
Дата: 14.03.03 19:51
Оценка: 18 (2)
Есть такая функция (она легендарная. Я вот имя не помню )
           _
          | b + 1                 при a = 0
f(a, b)= -| f(a - 1, 1)           при b = 0
          |_f(a - 1, f(a - 1, 1)) в других случаях

Как избавится от рекурсии для ее вычисления?

Заранее благодарю.

15.03.03 14:22: Перенесено из 'Алгоритмы'
Re: Избавление от рекурсии
От: adontz Грузия http://adontz.wordpress.com/
Дата: 14.03.03 21:48
Оценка:
Здравствуйте, MikaRSDN Soukhov, Вы писали:

Если тебя интересует формальное избавление от рекурсии то не знаю.

Если просто волнует время вычисления, тое сть стандартный способ
Имеем записи
a b f(a,b)
Если нужное нам значение есть в таблице, то берём из таблицы.
Если нужного нам значения нет в таблице, то вычисляем его и заносим в таблицу.
Для данных a, b ни одно значение функции не будет считаться дважды
Время работы и необходимая память (могу ошибаться) О(a+b)
A journey of a thousand miles must begin with a single step © Lau Tsu
Re: Избавление от рекурсии
От: klovetski Россия  
Дата: 15.03.03 09:31
Оценка: 7 (1)
Здравствуйте, MikaRSDN Soukhov,

Общие методы избавления от рекурсии (и очень похожий пример)
глава 8, параграф 3:
(zipped pdf , 650 K)
ftp://ftp.mccme.ru/users/shen/logic/comput/part3pdf.zip

и оно же, но (gzipped postscript , 320 K),
ftp://ftp.mccme.ru/users/shen/logic/comput/part3.ps.gz
Re: Избавление от рекурсии
От: MichaelP  
Дата: 17.03.03 09:26
Оценка: 12 (1)
Здравствуйте, MikaRSDN Soukhov, Вы писали:

MS>Есть такая функция (она легендарная. Я вот имя не помню )

MS>
MS>           _
MS>          | b + 1                 при a = 0
MS>f(a, b)= -| f(a - 1, 1)           при b = 0
MS>          |_f(a - 1, f(a - 1, 1)) в других случаях

MS>

MS>Как избавится от рекурсии для ее вычисления?

MS>Заранее благодарю.


Или автор что-то напутал, или я где-то ошибся, или функция раскрывается так:
int f(int a, int b)
{
  if(a==0)
    return b+1;
  if((b==0) && (a==1))
    return 2;
  return 3;
}
Re: Избавление от рекурсии
От: Кодт Россия  
Дата: 17.03.03 09:48
Оценка: 32 (3)
Здравствуйте, MikaRSDN Soukhov, Вы писали:

MS>
MS>           _
MS>          | b + 1                 при a = 0
MS>f(a, b)= -| f(a - 1, 1)           при b = 0
MS>          |_f(a - 1, f(a - 1, 1)) в других случаях

MS>

MS>Как избавится от рекурсии для ее вычисления?

Среди аргументов функции есть особые значения: 0 и 1 (0 — является селектором, 1 — подставляется при рекурсии).
Исследуем поведение...

f(0,0) = 1
f(0,1) = 2
f(0,b) = b+1 // b >= 1

f(1,0) = f(0,1) = 2
f(1,1) = f(0,f(0,1)) = f(0,2) = 3
f(1,b) = f(0,f(0,1)) = f(0,2) = 3 // b >= 1

f(a,0) = f(a-1,1)
f(a,1) = f(a-1,f(a-1,1))
f(a,b) = f(a-1,f(a-1,1)) // b >= 1

Заметим, что (для неотрицательных a, b) f = { 1,2,3 }.
Поэтому все последние варианты сведутся к вызову функции f(a-1,???) = f(a-2,???) = ... = f(1,???) = 3

Теперь разберемся с отрицательными значениями.
f(0,-b) = 1-b
f(1,-b) = f(0,f(0,1)) = f(0,2) = 3
f(+a,-b) = f(a-1,f(a-1,1)) = f(a-1,???) = ... = f(1,???) = 3
f(-a,b) = f(-a-1,f(-a-1,1)) = ... бесконечное зацикливание до переполнения ... = f(0,f(0,...f(0,1)) = 1*(INT_MAX+a)+1

Вот и все. И никакой рекурсии.
f(int a, int b)
{
  if(a==0) return b+1;
  if(a==1 && b==0) return 2;
  if(a < 0)
  {
    int c = 1;
    for(; a < 0; --a) ++c; // для полноты моделирования :)))
    return c;
  }
  return 3;
}
Перекуём баги на фичи!
Re[2]: Избавление от рекурсии
От: Кодт Россия  
Дата: 17.03.03 09:50
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Или автор что-то напутал, или я где-то ошибся, или функция раскрывается так:

MP>
MP>int f(int a, int b)
MP>{
MP>  if(a==0)
MP>    return b+1;
MP>  if((b==0) && (a==1))
MP>    return 2;
MP>  return 3;
MP>}
MP>

Молодец! Ты приходишь на работу на полчаса раньше меня
Перекуём баги на фичи!
Re[3]: Избавление от рекурсии
От: MichaelP  
Дата: 17.03.03 09:54
Оценка:
Здравствуйте, Кодт, Вы писали:

К> Молодец! Ты приходишь на работу на полчаса раньше меня


Зато я не додумался так здорово разобраться с отрицательными числами
Re: Избавление от рекурсии
От: mihoshi Россия  
Дата: 17.03.03 15:58
Оценка:
Здравствуйте, MikaRSDN Soukhov, Вы писали:

MS>Есть такая функция (она легендарная. Я вот имя не помню )

MS>
MS>           _
MS>          | b + 1                 при a = 0
MS>f(a, b)= -| f(a - 1, 1)           при b = 0
MS>          |_f(a - 1, f(a - 1, 1)) в других случаях

MS>

MS>Как избавится от рекурсии для ее вычисления?

В машинных кодах нет рекурсии. Соответственно, все рекурсия приводятся к итерация. Естественный образ — с помощью стека.
Re[2]: Избавление от рекурсии
От: MikaRSDN Soukhov Stock#
Дата: 17.03.03 16:30
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Здравствуйте, MikaRSDN Soukhov, Вы писали:


MS>>Есть такая функция (она легендарная. Я вот имя не помню )

MS>>
MS>>           _
MS>>          | b + 1                 при a = 0
MS>>f(a, b)= -| f(a - 1, 1)           при b = 0
MS>>          |_f(a - 1, f(a - 1, 1)) в других случаях

MS>>

MS>>Как избавится от рекурсии для ее вычисления?

MS>>Заранее благодарю.


MP>Или автор что-то напутал

[skipped]
Напутал

           _
          | b + 1                 при a = 0
f(a, b)= -| f(a - 1, 1)           при b = 0
          |_f(a - 1, f(a - 1, b)) в других случаях
Re[3]: Избавление от рекурсии
От: MichaelP  
Дата: 17.03.03 17:26
Оценка:
Здравствуйте, MikaRSDN Soukhov, Вы писали:

MS>
MS>           _
MS>          | b + 1                 при a = 0
MS>f(a, b)= -| f(a - 1, 1)           при b = 0
MS>          |_f(a - 1, f(a - 1, b)) в других случаях
MS>


Ну, тогда совсем по другому
unsigned int f(unsigned int a, unsigned int b)
{
  if(b==0)
  {
    if(a==0)
      return 1;
    return 2;
  }
  return b+1;
}
Re[4]: Избавление от рекурсии
От: MikaRSDN Soukhov Stock#
Дата: 17.03.03 19:17
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Ну, тогда совсем по другому

MP>
MP>unsigned int f(unsigned int a, unsigned int b)
MP>{
MP>  if(b==0)
MP>  {
MP>    if(a==0)
MP>      return 1;
MP>    return 2;
MP>  }
MP>  return b+1;
MP>}
MP>


Да, в этот раз совсем по другому... В этот раз у тебя не работает
int f(int a, int b)
{
  if (a == 0)
    return b + 1;
  else if (b == 0)
    return f(a - 1, 1);
  else
    return f(a - 1, f(a - 1, b));
}


Эта ф-ия при a == 9 && b == 1 возвращает 513. А у тебя что? 2. Разница хоть и маленькая но хотелось бы поточнее
Re[5]: Избавление от рекурсии
От: MichaelP  
Дата: 18.03.03 07:44
Оценка: 46 (2)
Здравствуйте, MikaRSDN Soukhov, Вы писали:


MS>Да, в этот раз совсем по другому... В этот раз у тебя не работает

MS>
MS>int f(int a, int b)
MS>{
MS>  if (a == 0)
MS>    return b + 1;
MS>  else if (b == 0)
MS>    return f(a - 1, 1);
MS>  else
MS>    return f(a - 1, f(a - 1, b));
MS>}
MS>


MS>Эта ф-ия при a == 9 && b == 1 возвращает 513. А у тебя что? 2. Разница хоть и маленькая но хотелось бы поточнее


Был неправ, исправляюсь:
unsigned int f(unsigned int a, unsigned int b)
{
  if(a==0)
    return b+1;
  if(b==0)
    return (1<<(a-1))+1;
  return (1<<a) + b; 
  
}
Re[2]: Избавление от рекурсии
От: Кодт Россия  
Дата: 18.03.03 08:37
Оценка: 10 (2)
Здравствуйте, mihoshi, Вы писали:

M>В машинных кодах нет рекурсии. Соответственно, все рекурсия приводятся к итерация. Естественный образ — с помощью стека.


Можно ввести определение, отличающие рекурсию от итерации.

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

Итерационные алгоритмы суть конечные автоматы (пусть даже с очень большим количеством состояний).
Рекурсивные — магазинные автоматы.

Разумеется, если рассмотреть машину целиком, то она является автоматом с гигантским количеством микросостояний (2^количество_триггеров_в_памяти_и_процессоре). И поэтому такой подход непродуктивен.
Перекуём баги на фичи!
Re[2]: Избавление от рекурсии
От: Balancer Россия http://balancer.da.ru
Дата: 18.03.03 12:05
Оценка:
A>Время работы и необходимая память (могу ошибаться) О(a+b)

Для функции Аккермана от трёх аргументов, примерно подобного порядка, для ackr(3,3,8) требуется таблица около 16млн записей, или индекс элементов достигает 16млн, если память не изменяет. В общем, таблично её вычисление ускорить не удалось
...Глубина-глубина, я не твой...
Re[6]: Избавление от рекурсии
От: MikaRSDN Soukhov Stock#
Дата: 18.03.03 12:26
Оценка:
Здравствуйте, MichaelP, Вы писали:

А если я еще раз скажу, что был не прав. Я еще раз ошибся в ф-ии

Вот ее нормальное описание
           _
          | b + 1                 при a = 0
f(a, b)= -| f(a - 1, 1)           при b = 0
          |_f(a - 1, f(a, b - 1)) в других случаях
Re[7]: Избавление от рекурсии
От: MichaelP  
Дата: 18.03.03 13:16
Оценка:
Здравствуйте, MikaRSDN Soukhov, Вы писали:

MS>Здравствуйте, MichaelP, Вы писали:


MS>А если я еще раз скажу, что был не прав. Я еще раз ошибся в ф-ии


MS>Вот ее нормальное описание

MS>
MS>           _
MS>          | b + 1                 при a = 0
MS>f(a, b)= -| f(a - 1, 1)           при b = 0
MS>          |_f(a - 1, f(a, b - 1)) в других случаях
MS>


Тогда скажу, что мы с третьей попытки дошли наконец до функции Аккермана , которая специально была придумана как "неизбавимая" от длинной рекурсии .
Re[8]: Избавление от рекурсии
От: MikaRSDN Soukhov Stock#
Дата: 18.03.03 13:25
Оценка:
Здравствуйте, MichaelP, Вы писали:

Тоесть, она решаема или не решаема?
Re[9]: Избавление от рекурсии
От: Balancer Россия http://balancer.da.ru
Дата: 19.03.03 08:54
Оценка:
MS>Тоесть, она решаема или не решаема?

Я видел решение для своего вида функции Аккермана (трёхпараметрической, формулу на память не помню, но отличается не принципиально) с развёрткой рекурсии в пару циклов. Вот только на VC7 вариант с циклами считался в несколько раз медленнее, чем рекурсивный.
...Глубина-глубина, я не твой...
Re[10]: Избавление от рекурсии
От: MikaRSDN Soukhov Stock#
Дата: 19.03.03 13:10
Оценка:
Здравствуйте, Balancer, Вы писали:

MS>>Тоесть, она решаема или не решаема?


B>Я видел решение для своего вида функции Аккермана (трёхпараметрической, формулу на память не помню, но отличается не принципиально) с развёрткой рекурсии в пару циклов. Вот только на VC7 вариант с циклами считался в несколько раз медленнее, чем рекурсивный.


Запостишь?
Re[11]: Избавление от рекурсии
От: Дмитро  
Дата: 01.04.03 11:47
Оценка: 12 (1)
Здравствуйте, MikaRSDN Soukhov, Вы писали:

MS>Здравствуйте, Balancer, Вы писали:


MS>>>Тоесть, она решаема или не решаема?


B>>Я видел решение для своего вида функции Аккермана (трёхпараметрической, формулу на память не помню, но отличается не принципиально) с развёрткой рекурсии в пару циклов. Вот только на VC7 вариант с циклами считался в несколько раз медленнее, чем рекурсивный.


MS>Запостишь?


Несмотря на то, что много воды уже утекло с тех пор, я запостю свой нерекурсивный вариант функции Аккермана в последней (и, наверное, окончательной) постановке.
ak(0, b) = b+1
ak(a, 0) = ak(a-1, 1)
ak(a, b) = ak(a-1, ak(a, b-1))


Этот нерекурсивный вариант работает быстрее рекурсивной реализации "в лоб". Это связано с тем, что не вычисляются лишний раз промежуточные значения. Расход памяти пропорционален параметру a. Для первых четырех значений a можно вывести формулы
ak(0, b) = b+1
ak(1, b) = b+2
ak(2, b) = 2*b+3
ak(3, b) = 2^b-3

Для значений a больших 3, функция Аккермана настолько быстро растет, что врядли, кому-то понадобится ее считать. Хотя, кто знает... может, у кого-то есть формулы в общем виде?

Да, код писался в расчете на удобную верификацию, но доказательство я не привожу (места на полях не хватает).

integer akerman(integer a, integer b) {
    struct Item {
        integer m_b;
        integer m_ak;
    };
    Item *array = new Item[a+1];
    for(integer i=0; i<a; ++i) {
        array[i+1].m_b = -1;
        array[i+1].m_ak = 1;
    }
    array[0].m_b = -1;
    array[0].m_ak = 0;
    while(array[a].m_b != b) {
        array[0].m_b++;
        array[0].m_ak++;
        for(integer i=0; (i != a) && (array[i].m_b == array[i+1].m_ak); ++i) {
            array[i+1].m_b++;
            array[i+1].m_ak = array[i].m_ak;
        }
    }
    integer result = array[a].m_ak;
    delete[] array;
    return result;
}


--
Дмитрий
--
Дмитрий
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.