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

         

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


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

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

  1. базис индукции: 0!=1;
  2. шаг индукции: 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;



Содержание раздела