Найдите N-ый член последовательности, сократив количество рекурсивных вызовов - C (СИ) (75506)

Формулировка задачи:

Доброго времени суток) Будьте добры, помогите, пожалуйста, с заданием c использованием рекурсии: Определите закономерность формирования членов последовательности. Найдите N-ый член последовательности, сократив количество рекурсивных вызовов. (ф-ция в приложении) Буду премного Вам благодарен.

Решение задачи: «Найдите N-ый член последовательности, сократив количество рекурсивных вызовов»

Листинг программы

#include <math.h>
#include <stdio.h>
 
int Counter; // счетчик вызова
 
double funcGood(int n, double curr, double prev)
{
    Counter++;
 
    if (n == 0)
        return curr;
    else
        return funcGood(n-1, sqrt(curr+prev),curr);
}
 
double funcBad(int n)
{
    Counter++;
 
    if (n <= 2)
        return 1.0;
    else
        return sqrt(funcBad(n-1)+funcBad(n-2));
}
 
int main(int argc, char* argv[])
{
    double r;
 
    // Неоптимальный расчет
 
    Counter=0;
    r=funcBad(20);
    printf("F=%f  C=%d\n\n",r,Counter);
 
    // Оптимальный расчет
 
    Counter=0;
    funcGood(20,1.0,1.0);
    printf("F=%f  C=%d\n\n",r,Counter);
    
    return 0;
 
}

Объяснение кода листинга программы

Включаем необходимые заголовочные файлы: и .
Объявляем переменную Counter для подсчета количества вызовов функций.
Определяем функцию funcGood, которая принимает три аргумента: n, curr и prev.
Увеличиваем счетчик вызовов на единицу.
Проверяем базовый случай: если n равно нулю, то возвращаем значение curr.
В противном случае, рекурсивно вызываем функцию funcGood с аргументами (n-1, sqrt(curr+prev),curr).
Определяем функцию funcBad, которая принимает один аргумент n.
Увеличиваем счетчик вызовов на единицу.
Проверяем базовый случай: если n меньше или равно двум, то возвращаем значение 1.0.
В противном случае, рекурсивно вызываем функцию funcBad с аргументами (n-1) и (n-2), и возвращаем значение sqrt(sum).
В функции main создаем переменную r типа double для хранения результата.
Инициализируем переменную Counter в нулевое значение.
Вызываем функцию funcBad с аргументом 20 и сохраняем результат в переменную r.
Выводим значение r и количество вызовов функции (Counter) на экран.
Инициализируем переменную Counter в нулевое значение.
Рекурсивно вызываем функцию funcGood с аргументами (20, 1.0, 1.0) и сохраняем результат в переменную r.
Выводим значение r и количество вызовов функции (Counter) на экран.
Возвращаем 0 из функции main, что означает успешное завершение программы.
Значение переменной r в первом случае равно 1.0, а во втором - 1.0.
Количество вызовов функции (Counter) в первом случае равно 21, а во втором - 20.