1. Основные понятия алгоритмизации и программирования

Косвенная рекурсия возникает в том случае, когда две или более функций вызывают друг друга. В случае двух функций: некоторая функция обращается к другой функции, а та в свою очередь вызывает первоначальную функцию. Для предотвращения зацикливания одна или обе функции должны проверять условие завершения.
Пример: Составить рекурсивную функцию, вычисляющую факториал числа n по формуле (учесть, что 0! = 1):

long fact (long n)
{
if (n==0 || n == 1) return 1;
return (n*fact(n-l));
}
То же самое можно записать короче:
long fact (long n)
{
return (n > 1) ? n*fact(n-l) : 1;
}
Пример: Распечатать последовательность, состоящую из n букв А и n букв В.
void abn (int n)
{
Console.WriteLine(“A”);
if (n > 1) abn(n-l);
Console.WriteLine(“B”);

}

Лабораторная работа №6

Программирование рекурсивных алгоритмов

ЦЕЛЬ РАБОТЫ: закрепление навыков программирования с использованием рекурсивных функций.
Выполнение работы: в соответствии с вариантом, используя прямую рекурсию, составить и реализовать программу.

Задание

1. 
   Описать рекурсивную функцию NOD(A, B) целого типа, находящую наибольший общий делитель (НОД) двух целых положительных чисел A и B, используя алгоритм Евклида: НОД(A, B) = НОД(B, A mod B), если B ≠ 0;  НОД(A, 0) = A. С помощью этой функции найти НОД(A, B), НОД(A, C), НОД(A, D), если даны числа A, B, C, D.
   
2. 
   Для n = 12 найти числа Фибоначчи. Числа Фибоначчи: F(0) = 1, F(1) = 1 F(n) = F(n - 2) + F(n - l)
   
3. 
   Даны целые числа m и n, где 0 ≤ m ≤ n, вычислить, используя рекурсию, число сочетаний С(n, m) по формуле: , при 0 ≤ m ≤ n. Воспользовавшись формулой можно проверить правильность результата.
   
4. 
   Опишите рекурсивную функцию, которая по заданным вещественному х и целому п вычисляет величину хⁿ согласно формуле:
   

5. 
   Задана последовательность положительных чисел, признаком конца которых служит отрицательное число. Используя рекурсию, подсчитать количество чисел и их сумму.
   
6. 
   Напишите рекурсивную функцию K(n), которая возвращает количество цифр в заданном натуральном числе n, используя формулу:
   

7. 
   Определим функцию S(n), вычисляющую сумму цифр заданного натурального числа:
   

Описать рекурсивную функцию DigitSum(K) целого типа, которая находит сумму цифр целого числа K, не используя оператор цикла. С помощью этой функции найти суммы цифр для пяти данных целых чисел.

8. 
   Дан вектор X из n вещественных чисел. Найти минимальный элемент вектора, используя вспомогательную рекурсивную функцию, находящую минимум среди элементов вектора X, начиная с n -гo.
   
9. 
   Напишите рекурсивную функцию для нахождения биномиальных коэффициентов (для заданного М ≥ i ≥ j > 0 вычислите все ):
   

10. 
    Напишите программу вычисления функции Аккермана для всех неотрицательных целых аргументов т и п:
    

11. 
    Для заданных границ интегрирования а и b вычислите значение определенного интеграла следующего вида:
    

12. 
    Для заданных границ интегрирования а и b вычислите значение определенного интеграла следующего вида:
    

13. 
    Для заданных границ интегрирования а и b вычислите значение определенного интеграла следующего вида:
    

14. 
    Для заданных границ интегрирования а и b вычислите значение определенного интеграла следующего вида:
    

15. 
    Для заданных границ интегрирования а и b вычислите значение определенного интеграла следующего вида:
    

16. 
    Для заданных границ интегрирования а и b вычислите значение определенного интеграла следующего вида:
    

17. 
    Для заданных границ интегрирования а и b вычислите значение определенного интеграла следующего вида:
    

18. 
    Для заданных границ интегрирования а и b вычислите значение определенного интеграла следующего вида:
    

19. 
    Для заданных границ интегрирования а и b вычислите значение определенного интеграла следующего вида:
    

20. 
    Для заданных границ интегрирования а и b вычислите значение определенного интеграла следующего вида:
    

21. 
    Для заданных границ интегрирования а и b вычислите значение определенного интеграла следующего вида:
    

22. 
    Для заданных границ интегрирования а и b вычислите значение определенного интеграла следующего вида:
    

23. 
    Для заданных границ интегрирования а и b вычислите значение определенного интеграла следующего вида:
    

24. 
    Для заданных границ интегрирования а и b вычислите значение определенного интеграла следующего вида:
    

25. 
    Напишите рекурсивную функцию, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения.