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

Question

我正在解决 99 problems of Ocaml 中的问题 4，我仍在学习 OCaml

第4题阅读

OCaml standard library has List.length but we ask that you reimplement it. Bonus for a tail recursive solution.

因此，根据我的理解，递归解决方案值得加分，因为它比可能更简单、更冗长的解决方案更有效

我想出了一个尾递归解决方案

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

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

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

因此，非尾递归函数可以是在递归调用之后执行任何操作的任何函数（或者甚至有多个不互斥的递归调用）。通常这意味着在递归函数 returns.

之后将一些其他函数应用于递归函数的结果

length 的非尾递归版本是：

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

这不是尾递归，因为这里发生的最后一件事是加法，而不是对 length 的调用。所以在递归调用 returns 之后，我们将其结果加 1，然后然后我们也 return。

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

What is the opposite of a tail recursive solution?

ocaml

functional-programming