Understanding Recursive Lookups in Cisco routing tables

First, the term "Recursive"

While recursion can just refer generically to repetition, the term in Information Systems and Technology contexts almost always refers to using a tool to enable the use of the same tool. Think of using a mirror to reflect a mirror (an example of infinite recursion).
Examples: 

1) A DNS server receives a DNS query for which it doesn't know the answer. It performs recursion by sending it's own DNS query to root DNS server to discover the answer for the client.

• DNS uses DNS to answer DNS.

2) In a Microsoft SQL database server there is a database called Master that is recursively used by SQL to find and reference the high level properties of all the other attached databases that are used by end-users.

• SQL uses SQL to manage SQL.

Now for understanding Cisco routing recursion:

A Recursive lookup refers to routes for which the router must look up the connected route to a next-hop gateway in order to route the packet to its ultimate destination.

• The Router uses Routes to 
• a) find the next router in the route path and 
• b) to Route to the next Router

This is because in a routing table the gateway for a routed network can be defined as an interface or as an IP address.

Using an interface works great when the router is referring to directly connected routes like this:
Router4#show ip route
Gateway of last resort is not set

     172.16.0.0/30 is subnetted, 1 subnets
C       172.16.100.0 is directly connected, Serial0/0
C    192.168.1.0/24 is directly connected, FastEthernet0/0 

or to point-to-point links in which there is only one possible intended destination:

Router5(config)#ip route 192.168.0.0 255.255.0.0 se 0/0
Router5(config)#end
%SYS-5-CONFIG_I: Configured from console by console
Router5#show ip route

Gateway of last resort is not set

     172.16.0.0/16 is variably subnetted, 2 subnets, 2 masks
C       172.16.1.0/24 is directly connected, FastEthernet0/0
C       172.16.100.0/30 is directly connected, Serial0/0
S    192.168.0.0/16 is directly connected, Serial0/0

However, routes that reference an endpoint on multi-access networks like Ethernet or Frame Relay need a logical destination, since the physical interface could connect to many devices. This is where we see our standard routing entries that indicate an IP address as the gateway value:

Router4(config)#ip route 172.16.1.0 255.255.255.0 172.16.100.1
Router4(config)#end
%SYS-5-CONFIG_I: Configured from console by console
Router4#show ip route

Gateway of last resort is not set

     172.16.0.0/16 is variably subnetted, 2 subnets, 2 masks
S       172.16.1.0/24 [1/0] via 172.16.100.1
C       172.16.100.0/30 is directly connected, Serial0/0
C    192.168.1.0/24 is directly connected, FastEthernet0/0

So now you need to think like a router
1) You receive an incoming packet destined for 172.16.1.5
2) You find that the best route is the static route 172.16.1.0/24 (remember to always choose the longest subnet mask / slash notation that is a match)
3) You discover the gateway for that route is 172.16.100.1
4) As a router, you have multiple interfaces. Which one should you use to contact 172.16.100.1?
5) You look up 172.16.100.1 in the routing table
6) You find that the best route is the connected route 172.16.100.0/30
7) You forward the packet over the Serial 0/0 interface

You just used your routing table to figure out how to route the packet to the gateway you found in your routing table - Recursion!!!

Test Tip: Watch out for how this could apply to a gateway of last resort - your 0.0.0.0/0 route!

Hope this helps clear things up for everyone!