尾递归解决方案的相反是什么？

Question

我正在解决Ocaml 99 题中的第 4 题中的问题 4 ，并且我仍在学习 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
;;

但我的直觉告诉我，我错过了比这更明显的东西，第二个解决方案似乎需要太多工作，而第一个解决方案似乎更自然和简单，我错过了什么？

Answer 1

尾递归函数是一种递归函数，其中所有递归调用都发生在尾部位置。这意味着递归调用必须是函数的任何给定路径中发生的最后一件事。您问题中的所有递归函数都是尾递归的。

尾递归并不意味着在列表的尾部进行递归。事实上，尾递归函数根本不必涉及列表。

因此，非尾递归函数是在递归调用之后执行任何操作的任何函数（或者甚至存在不互斥的多个递归调用）。通常这意味着在递归函数返回后将一些其他函数应用于递归函数的结果。

的非尾递归版本length是：

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

这不是尾递归，因为这里发生的最后一件事是加法，而不是调用length. 因此，递归调用返回后，我们将其结果加 1，然后也返回。