Both the human brain and recent deep neural networks (DNNs) successfully perform object recognition. However, the visual pathway consists of far fewer hierarchical stages compared to those in DNNs. The structural factor that achieves efficient visual function of the brain is still elusive. Here, we suggest that cortical long-range horizontal connections (LRCs) observed in the early visual cortex enable cost-efficient object recognition in shallow network. First, to validate our hypothesis, a shallow network with convergent feedforward connections and LRCs from neural connectivity data of tree shrew was designed. To investigate effect of LRCs for object recognition, the network was trained for CIFAR-10 image classification by changing network connectivity. We found that addition of LRCs to the shallow feedforward network significantly enhances the classification performance, even to comparable to much deeper network. Second, from gradient-based optimization by pruning the connections, we confirmed that LRCs could spontaneously emerge by balancing between minimizing total connection length and maximizing classification performance. After the optimization, a certain portion of long-range connections survived. Deletion of survived LRCs led to significant reduction of classification performance, which implies LRCs are important for object recognition. Third, to investigate how LRCs contribute to image processing, datasets with local or global structure of input images were generated by modifying handwritten digit dataset. We observed that the network with sparse LRCs and dense feedforward connections can consistently classify images with different local and global information. Lastly, we found that performance enhancement by LRCs is strongly correlated with small-worldness of network, and that this can explain the species-specific existence of LRCs in the visual cortex. In summary, we suggest that long-range horizontal connectivity may be a key factor allowing the visual cortex to implement cost-efficient object recognition under physical constraints.