Является ли эта схема кода хвостовой рекурсивной?

Question

РЕДАКТИРОВАТЬ: Спасибо всем. Я новичок в языке (только начал использовать его два дня назад), поэтому я не знаком с conds. Я могу переписать его, если у меня будет время, но я просто хотел убедиться, что я правильно понял основную логику. Еще раз спасибо!

Мое назначение - создать хвостовую рекурсивную функцию, которая удаляет n-й элемент из списка, 1 <= n <= listlength, только с двумя параметрами, списком x и элементом n. Таким образом, (удалить 1 '(a b c d)) вернется (b c d). Я написал следующее и хотел бы получить некоторое заверение, что это действительно хвостовая рекурсия. Единственное, на чем я не совсем уверен, - это если рекурсивный вызов может быть вложен в оператор IF.

(define (remove n x)
  ; if n is 1, just return the cdr 
  (if (and (not (list? (car x))) (= n 1))
     (cdr x)
     ; if the car is not a list, make it one, and call recursively
     (if (not (list? (car x)))
        (remove (- n 1) (cons (list (car x)) (cdr x)))
        ; if n !=1, insert the cadr into the list at the car.
        ; Else, append the list at the car with the cddr
        (if (not(= n 1))
           (remove (- n 1) (cons (append (car x) (list(cadr x))) (cddr x)))
           (append (car x) (cddr x))))))

Answer 1

Да, процедура является хвост-рекурсивной, что означает: где бы ни выполнялся рекурсивный вызов, это последнее, что происходит в этой конкретной ветви выполнения, и после возврата рекурсии больше нечего делать - следовательно, мы говорим, что рекурсивный вызов в хвостовом положении.

Это хорошо видно, если переписать процедуру, используя cond вместо вложенных ifs, здесь вы увидите, что каждая ветвь выполнения приводит либо к базовому, либо к рекурсивному случаю, и все рекурсивные вызовы находятся в хвостовой позиции:

(define (remove n x)
         ; base case #1
  (cond ((and (not (list? (car x))) (= n 1))
         ; return from base case, it's not recursive
         (cdr x))
         ; recursive case #1
        ((not (list? (car x)))
         ; recursive call is in tail position
         (remove (- n 1) (cons (list (car x)) (cdr x))))
         ; recursive case #2
        ((not (= n 1))
         ; recursive call is in tail position
         (remove (- n 1) (cons (append (car x) (list(cadr x))) (cddr x))))
         ; base case #2
        (else
         ; return from base case, it's not recursive
         (append (car x) (cddr x)))))

Для более технического объяснения того, почему последующие / альтернативные части if специальную форму можно считать хвостовой рекурсивной, взгляните на раздел 3.5 текущего проекта пересмотренного Отчета об алгоритмической языковой схеме ^7 - спецификация языка, вот ссылка на файл pdf (по сути, те же соображения применимы к R5RS, просто они более подробно объясняются в R7RS). Особенно:

Если одно из следующих выражений находится в хвостовом контексте, то подвыражения, показанные как "хвостовое выражение", находятся в хвостовом контексте

...

(if ⟨expression⟩ ⟨tail expression⟩ ⟨tail expression⟩)

(if ⟨expression⟩ ⟨tail expression⟩)

Answer 2

Вот спецификация Scheme для позиции хвостовой рекурсии для синтаксических форм: