CODEWITHSUNDEEP
functional-programmingocaml
Srini
Srini

Reputation: 1639

What is the opposite of a tail recursive solution?

I'm solving problem 4 in the 99 problems of Ocaml and I'm still learning OCaml

Question 4 reads

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

So as per my understanding a recursive solution merits bonus points because it more efficient than a potentially easier more verbose solution

I came up with this 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
;;

And as per my understanding of tail recursion this is valid because it operates recursively on the tail

My question is what is the opposite of this? What is a valid non tail recursive solution

I guess it would be something that operates recursively on the head of the list I came up with 

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
;;

But my gut tells me I'm missing something more obvious than this and the second solution seems like too much work and the first seems more natural and easy, what am I missing?

Upvotes: 1

Views: 703

Answers (1)

sepp2k
sepp2k

Reputation: 370112

A tail-recursive function is a recursive function where all recursive calls happen in a tail position. What that means is that the recursive call must be the last thing that happens in any given path through the function. All of the recursive functions in your question are tail recursive.

Tail recursion does not mean recursing on the tail of the list. In fact a tail recursive function doesn't have to involve lists at all.

So a non-tail recursive function would be any function where you do anything after the recursive call (or there are even multiple recursive calls that aren't mutually exclusive). Usually that means applying some other function to the result of the recursive function after the recursive function returns.

A non-tail recursive version of length would be:

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

This is not tail-recursive because the last thing that happens here is the addition, not the call to length. So after the recursive call returns, we add 1 to its result and then we return as well.

Upvotes: 5

Related Questions