Введение в теорию программирования. Функциональный подход

Рекурсивные вычисления

Показывать лекцию целиком

Теоретические сведения

Рекурсивно определенная функция содержит в своем определении ссылку на саму себя. Важными областями примемения индукции в математике являются индуктивные определения и доказательства.

Рекурсия в языке программирования SML определяется по аналогии с традиционной математической индукцией. Например, определение функции вычисления факториала в терминах математической индукции имеет вид:

  • базис индукции: 0!=1 ;
  • шаг индукции: n!=n*(n-1)!.
    •

    Программный проект, реализующий соответствующую функцию на языке на SML, имеет вид:

    structure Project2
: sig val main: string option array 
  option -> unit
end =
struct
     
fun factorial 0 = 1 | 
  factorial (n:int) = n * factorial (n-1);
fun main (a : string option array option) =
  (*@TODO: add your code here *)
(
  print ("factorial(4) = 
         " ^ Int.toString(factorial(4)) ^ "\n"
)
end

    Пользуясь условным выражением if языка программирования SML, функцию вычисления факториала можно представить следующим фрагментом программы:

    fun factorial n = if (n<2) 
then 1 else n * factorial(n-1);

    Возможно рекурсивное определение не только функций, но и типов.

    Например, определение списочного типа на языке SML имеет вид:

    datatype slist = 
    nil | element of char * slist;

    Задание

    Сформулируйте формальную постановку задачи, запишите правила вывода и реализуйте программу на SML в соответствии с вариантом исполнения.

    Реализовать на языке SML следующие рекурсивные функции:

  • Предшествования для целых чисел.
  • Следования для целых чисел.
  • Суммы первых N чисел натурального ряда.
  • Произведения первых N чисел натурального ряда (факториала).
  • Вычисления чисел Фибоначчи.
  • Решения задачи о размещении 8 ферзей на шахматной доске 8х8 так, чтобы никакой из них они не "бил" другого.
  • Решения задачи о "Ханойских башнях".
  • Упорядочения массива.
  • Обхода двоичного дерева слева.
  • Обхода двоичного дерева справа.
  • "Балансировки" двоичного дерева
  • Подсчета количества элементов двоичного дерева.
  • Упорядочения списка.
  • Вставки элементов в упорядоченный список.
  • Вставки элементов в "сбалансированное" двоичное дерево.
  • Наибольшего общего делителя по алгоритму Евклида.
  • Суммы N элементов арифметической прогрессии.
  • Суммы N элементов геометрической прогрессии.
  • Решения задачи о ханойских башнях (перемещение диска со стержня А на стержень В отображать посредством вывода текста " А->В ").
  • Суммы элементов списка.
  • Инвертирования списка.
  • Произведения с использованием только функции сложения.
  • Суммы с использованием только функции прибавления единицы.
    •
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^