Applications such as streaming multimedia, Voice over IP (VoIP) and video teleconferencing require quality of service (QoS), and developing algorithms that find routes from a source to a destination which meet the users' QoS requirements under rapidly changing network conditions remains a technical challenge. Recently, the cognitive packet network (CPN) has been proposed so as to offer adaptive QoS driven routing based on on-line sensing and monitoring. In this paper, we propose a recursive routing algorithm for CPN which breaks large scale route discovery problems into smaller ones. The solutions to those smaller routing problems arc cached in the intermediate nodes of the network, which can be utilized by Smart Packets to solve larger scale routing problems. The experiments conducted on a 46-node network test-bed indicate that when recursive routing is deployed, the network connection establishment time can be drastically reduced without sacrificing the QoS of the routes discovered, and that the QoS that the users experience is also improved.