An efficient caching can be achieved by predicting the popularity of the files accurately. It is well known that the popularity of a file can be nudged by using recommendation, and hence it can be estimated accurately leading to an efficient caching strategy. Motivated by this, in this paper, we consider the problem of joint caching and recommendation in a 5G and beyond heterogeneous network. We model the influence of recommendation on demands by a Probability Transition Matrix (PTM). The proposed framework consists of estimating the PTM and use them to jointly recommend and cache the files. In particular, this paper considers two estimation methods namely a) Bayesian estimation and b) a genie aided Point estimation. An approximate high probability bound on the regret of both the estimation methods are provided. Using this result, we show that the approximate regret achieved by the genie aided Point estimation approach is $\mathcal{O}(T^{2/3} \sqrt{\log T})$ while the Bayesian estimation method achieves a much better scaling of $\mathcal{O}(\sqrt{T})$. These results are extended to a heterogeneous network consisting of M small base stations (sBSs) with a central macro base station. The estimates are available at multiple sBSs, and are combined using appropriate weights. Insights on the choice of these weights are provided by using the derived approximate regret bound in the multiple sBS case. Finally, simulation results confirm the superiority of the proposed algorithms in terms of average cache hit rate, delay and throughput.