Что является противоположностью хвостового рекурсивного решения? - PullRequest
Новая
       10

Что является противоположностью хвостового рекурсивного решения?

0 голосов
/ 01 апреля 2020

Я решаю проблему 4 в 99 задачах Ocaml , и я все еще изучаю OCaml

Вопрос 4:

В стандартной библиотеке OCaml есть List.length, но мы просим вас переопределить его. Бонус за хвостовое рекурсивное решение.

Так что, по моему пониманию, рекурсивное решение заслуживает бонусных баллов, потому что оно более эффективно, чем потенциально более простое и подробное решение

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

let length in_list =
  let rec find_len cur_length = function
  | [] -> cur_length
  | hd::tl -> find_len (cur_length + 1) tl
  in find_len 0 in_list
;;

И в соответствии с моим пониманием рекурсии хвоста это верно, потому что оно действует рекурсивно на хвосте

Мой вопрос, что является противоположностью этому? Какое реальное не хвостовое рекурсивное решение

Полагаю, это будет что-то рекурсивное в начале списка, который я придумал 

let hd_rec_length in_list =
  let rec pop_last saved_list= function
  | [] -> saved_list
  | [last] -> saved_list
  | hd::tl -> pop_last (saved_list@[hd]) tl
  in 
    let rec hd_rec_find_len cur_length in_list =
    match in_list with  
      | [] -> cur_length
      | hd::tl -> hd_rec_find_len (cur_length+1) (pop_last [] in_list)
      in hd_rec_find_len 0 in_list
;;

Но моя интуиция говорит мне Я упускаю что-то более очевидное, чем это, и второе решение кажется слишком трудоемким, а первое кажется более естественным и простым, чего мне не хватает?

1 Ответ

3 голосов
/ 01 апреля 2020

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

Хвостовые рекурсии не означают повторения в конце списка. Фактически, хвостовая рекурсивная функция вообще не должна включать списки.

Так что не хвостовая рекурсивная функция будет любой функцией, в которой вы делаете что-либо после рекурсивного вызова (или есть даже несколько рекурсивных вызовов, которые не являются взаимоисключающими). Обычно это означает применение какой-либо другой функции к результату рекурсивной функции после ее возвращения.

Не хвостовая рекурсивная версия length будет выглядеть так: 

let rec length = function
| [] -> 0
| _::tl -> 1 + length tl

Это не рекурсивно, потому что последнее, что здесь происходит, это добавление, а не вызов length. Поэтому после возврата рекурсивного вызова мы добавляем 1 к его результату и , затем также возвращаем.

...