#Haskell, <s>154</s> <s>149</s> <s>147</s> <s>145</s> <s>128</s> <s>120</s> <s>119</s> 117 bytes

    import Data.List
    (r%x)n|n>0&&r<":"=[(r\\t)%(x++(show n\\t))$n-1|t<-tails x,isPrefixOf t$show n]!!0|0<1=x
    h=['0'..]%""

adding in the recycling-checking cost <b>a lot</b> of characters... sigh

golfed a bit by remembering what digits weren't recycled yet and stopping when the list is empty. then golfed a bit more by moving to explicit recursion and a few more tricks.

example output:
   
    *Main> h 110
    "110910810710610510410310210100998979695949392919089887868584838281807978776757473727170696867665646362616059585756554535251504948474645443424140393837363534332313029282726252423221"