Trajectory planning in dynamic environments can be decomposed into two sub-problems: 1) planning a path to avoid static obstacles, 2) then planning a speed profile to avoid dynamic obstacles. This is also called path-speed decomposition. In this work, we present a novel approach to solve the first sub-problem, motion planning with static obstacles. From an optimization perspective, motion planning for autonomous vehicles can be viewed as non-convex constrained nonlinear optimization, which requires a good enough initial guess to start and is often sensitive to algorithm parameters. We formulate motion planning as convex spline optimization. The convexity of the formulated problem makes it able to be solved fast and reliably, while guaranteeing a global optimum. We then reorganize the constrained spline optimization into a recurrent formulation, which further reduces the computational time to be linear in the optimization horizon size. The proposed method can be applied to both trajectory generation and motion planning problems. Its effectiveness is demonstrated in challenging scenarios such as tight lane changes and sharp turns.