Теоретические сведения
Рекурсивно определенная функция содержит в своем определении ссылку на саму себя. Важными областями примемения индукции в математике являются индуктивные определения и доказательства.
Рекурсия в языке программирования 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;
