Can all structurally recursive functions be written without explicit recursion using a catamorphism/fold?
Your function is completely structurally recursive on n, so it is pretty much just a change of notation to make it a catamorphism on the natural numbers.

type nat = Z | S of nat 

(* cata : α → (α → α) → nat → α *)                      
let rec cata z s = function
  | Z -&gt; z 
  | S n -&gt; s (cata z s n)

(* halting_search : nat → (α → bool) → (α → α) → α → α option *)             
let halting_search n = 
  cata (fun test next seed -&gt; None)
       (fun recur test next seed -&gt; 
         if test seed then 
           Some seed
         else 
           recur test next (next seed))
       n


For languages with higher-order functions and strictly positive datatypes, having a fold is equivalent in expressive power to permitting structural recursion. However, it is not equivalent in terms of efficiency. If you just have fold, then implementing the predecessor function on the Peano natural numbers is O(n), whereas if you have a case form, it is O(1). 

(* This is linear time! *)
pred : nat -&gt; nat option 
let pred n = cata None (function 
                           | None   -&gt; Some Z 
                           | Some n -&gt; Some (S n)) n