Python 2 (38) (43)

f=lambda n:n*'_'and f(~-n/10)+`~-n%10` 

No character substitution, just arithmetic.

I use ~-n to compute n-1 with higher precedence than /10 or %10, saving on parens. The n*'_' is just to produce the empty string when n=0 and any other string otherwise. The '_' can be any string for this purpose.

Ungolfed:

def f(n): if n==0: return '' else: return f((n-1)//10) + str((n-1)%10) 

I don't have a good reason why the recursion works, I just fit this pattern to the list of values. If you changed each n-1 to n, you'd get the regular digit representation.