posicion - obtener el primer elemento de una lista en java

Encontrar un elemento en una lista y devolver su índice-OCaml

Question

He escrito la siguiente función para encontrar un elemento dado "x" en una lista dada "lst" y devolver su índice si se encuentra, de lo contrario devolvería un error:

exception Failure of string
let rec func x lst c = match lst with
| [] -> raise(Failure "Not Found")
| hd::tl -> if (hd=x) then c else func x tl (c+1)
let find x lst = func x lst 0

La función está funcionando completamente, solo me pregunto cuál es el consumo de memoria de ella. ¿Significa que el consumo de memoria depende de la longitud de la lista? o es O (1)?

Si no es O (1) ¿alguien puede decirme qué debo hacer para que así sea?

Gracias

Answer 1

Su función consume espacio constante (O (1)), porque es cola recursiva.

Puede leer sobre recursividad de cola en OCaml.org, aquí .

Actualizar

Aquí hay una solución sin recursividad de cola:

exception Failure of string
let rec find x lst =
match lst with
| [] -> raise (Failure "Not Found")
| h :: t -> if x = h then 0 else 1 + find x t

(Me di cuenta de que PatJ ya lo explicó, lo siento :-)

A menudo, la solución recursiva sin cola es más concisa y elegante. Es una lástima, pero así es el mundo a veces.