Unmanned aerial vehicles (UAVs) have attracted attention from both the academic and industry because of its highly controllable mobility. The UAV has hence become a potential alternative for a large amount of geographically distributed sensors in provisioning sensing service where the information of different locations (e.g., temperature, humidity, pollutant level and traffic condition) are sensed and sent to the ground station (GS). However, the UAV on-board battery is usually limited due to the size and weight constraints, and greatly affects the UAV performance. Practically, the UAV usually needs to return to the GS for recharging before the battery exhaustion. The trajectory routes, therefore, should be well designed to meet the battery capacity constraint and improve the quality of service (QoS). In this paper, we investigate the trajectory optimization of rechargeable UAV for sensing service to minimize the task completion latency. We formulate this problem as a mixed integer linear programming (MILP) model. A Clone Searching Algorithm (CSA), which clones the rechargeable UAV into several non-rechargeable virtual UAVs and simultaneously search trajectory routes for each virtual UAV, is then designed to reduce the computational complexity of MILP. Numerical results demonstrate the performance of our proposed algorithm.