Рекурсия, Си

[Аватар]

Вообще не вижу логики в этом коде. На бумажке с карандашом проследи что делает эта функция

[Алексей_2012]

 int main()
{

     cout << recursion(5);

    return 0;
}

почему нет логики?

сначала получается так:

5/6. Если введенное число меньше равно нулю, то возвращаем 1/, если нет, то к вычисленному а прибавляем результат от (Числа - 1), т.е. получеатся:

5/6+4/5+3/4+2/3+1/2+1

Так тоже не работает

#include <iostream>

using namespace std;

float recursion (int chislo)
{

 float a=chislo/(chislo+1);

    if (chislo>=1) return a+recursion(chislo-1);
}

 int main()
{

     cout << recursion(5);

    return 0;
}

[BDA]

1) int делить на int в результате даст int.
2) Последний вызов функции ничего не вернет - в результате общая сумма nan.

[Алексей_2012]

Ну в первом вопросе int на float.

А во втором? Чтоб убрать nan - нужно в условии поставить >=2

[rrrFer]

Алексей_2012
Ты пишешь рекурсивные функции неправильно.
Посмотри статью про анализ рекурсивных алгоритмов, там есть большое количество примеров. Если ты внимательно посмотришь эти примеры, то заметишь, что в рекурсивной функции всегда выделяется условие, при котором задача решается без рекурсивного вызова (тривиальное решение). Если такого условия нет, то рекурсия будет бесконечной.

Т.е. я вот беру код из первого поста:

int rabbits (int mounth)
{
    if (mounth<3) // условие тривиального решения
      return 1;  // тривиальное решение
    else // если задача не решается "сразу", то выполняем рекурсивные вызовы
        return
                rabbits(mounth-1)+
                rabbits(mounth-2);
    
}

Рекурсивные вызовы внутри рекурсивной функции должны выполняться над более простой задачей (над меньшим объемом данных). Ты можешь проследить это в куче примеров по ссылке или вот в твоем примере:
вызов rabbits(mounth-1) более простой, чем изначальный rabbits(mounth), т.к. объем данных сократился на единицу.

Ты явно не разобрался с этим, т.к. вот последний твой код:

float recursion (int chislo) {
 float a=chislo/(chislo+1);
 if (chislo>=1) return a+recursion(chislo-1);
}

Не содержит никакого нерекурсивного решения. Твоя функция тут вообще ничего не возвращает если chislo < 1. Ничего не возвращает, но должна вернуть дробное число и в этом ошибка.

Вобщем посмотри примеры рекурсивных функций и попробуй найти в них что-то общее. Для начала.

[Алексей_2012]

Окей, вроде переделал...работает, можно ли сделать лучше? Притом так, чтоб в параметрах функции было число типа int?

#include <iostream>

using namespace std;

float recursion(float chislo)
{
    if (chislo == 0) return 0; // Если ряд завершен, то возвращаем 0

    float a = chislo / (chislo + 1);

    cout<<a<<endl;
    return a + recursion(chislo - 1);
}

int main()
{
    cout <<   recursion(5.0);
    return 0;
}

[Stilet]

Притом так, чтоб в параметрах функции было число типа int?

float recursion(int chislo)
{
    if (chislo == 0) return 0; // Если ряд завершен, то возвращаем 0

    float a = 1.0*chislo / (chislo + 1);

    cout<<a<<endl;
    return a + recursion(chislo - 1);
}

не?

[Алексей_2012]

Спасибо, а вот почему при i=1 выдается 1, а не 3?

#include <iostream>
#include <math.h> // для вызова pow

using namespace std;

float recursion(int chislo,int i)
{

if (i==0) return 0;
float a = pow((1.0*chislo),i)/(pow(1.0*3,i)*(i+1));
return a+recursion(chislo-1,i-1);
}

int main()
{
    cout << "Itog: "<< (1+recursion(3,3));
    return 0;
}

[BDA]

Или float a = chislo / (chislo + 1.0);.
По последнему коду - chislo это x? Тогда почему оно уменьшается?

[Алексей_2012]

Точно, опять моя невнимательность, тороплюсь сделать 10 рекурсий до после завтра.

А как закодить в функции то, что при i=1 нужно вычислить из 1 то/, что получилось на предыдущий итерации.

#include <iostream>
#include <math.h>

using namespace std;


float recursion(int x,int i)
{

    if(i==0) return 0;


    float a = pow(x,i) / pow(5,i)*sqrt(i+1);

   if (i % 2)
        return a + recursion(x,i - 1);
    else
        return -a + recursion(x,i - 1);
}

int main()
{
    cout<<recursion(5,5);
    return 0;
}

Или может быть из единицы вычесть функцию в main?

Все равно не получилось сделать так, чтоб в числителе было 5..3...1, а в знаменателе то же самая i, но с другими значениями

#include <iostream>
#include <math.h>

using namespace std;


float recursion(int x,int i)
{

    if(i==0) return 0;

    
    float chislitel=pow(1.0*x,i-1);
    float znaminatel =pow(1.0*5,i)*sqrt(i+1); 
    
        
    float a = chislitel  / znaminatel ;

   cout<<a<<endl;

   if (i % 2)
        return a + recursion(x,i - 1);
    else
        return -a + recursion(x,i - 1);
}

int main()
{
    cout<<"ITOG: "<<recursion(5,5);
    return 0;
}