Рекурсия по аргументу, пример

Функция называется рекурсией по аргументу, если ее рекурсивные вызовы определяют результат функции. Рекурсия по аргументу существует в функции, возвращаемое значение которой формирует некоторая не рекурсивная функция, в качестве аргумента которой используется рекурсивный вызов.

Пример: на Лиспе (Функция выделения из списка элемента с заданным номером)

>(defun nth1 (x l); функция возвращает элемент списка l,

; находящийся на позиции х от начала списка

(cond ((null l) nil); если список пустой, то возвратить NIL

((= x 0) (car l))

; если значение позиции х=0, то возвратить голову списка

(t (nth (- x 1) (cdr l))))

; в противном случае вызвать функцию nth1 у

; которой первый аргумент − значение позиции будет

; на единицу меньше, а второй аргумент хвост списка

)

>(nth1 2 ‘(a s d f g)); выделить второй элемент списка

D; нумерация элементов списка начинается с 0

В Эрланге

nth1(_,L) when L==[] -> [];

nth1(X,[H|_]) when X==0 -> H;

nth1(X,[_|T]) -> nth1((X-1),T).

2> recc:nth1(2,[a,s,d,f,g]).

D

Рекурсия по значению, пример

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

Пример: на лиспе

>(mem 'a '(b c a d e f))

T

> (defun mem (a list)(cond

((null list) nil);

((eql a (car list)) t);

(t (mem a (cdr list)))

))

На эрланге:

mem (_,[])->false;

mem (x,[x|_])->true;

mem (x,[Y|T))->mem(x,t).

Дата добавления: 2015-07-19