What could we the complexity proof of it?

Observe first that there are Θ(5^n/2) valid numbers of length n. Given the recurrence

C(−2) = 0
C(−1) = 0
C(0) = 1
C(1) = 3
∀n ≥ 2, C(n) = 5 N(n−2),

there are C(n) − C(n−2) numbers. If n = 2k where k is an integer, then C(n) = 5^k. If n = 2k + 1, then C(n) = 3 (5^k).

The running time is Θ(5^n/2 n). We can write a recurrence

T(0) = O(1)
T(1) = O(1)
∀n ≥ 2, T(n) = T(n−2) + Θ(5^n/2 n),

where the latter term counts the cost of constructing Θ(5^n/2) numbers each of length n. This is not a terribly interesting recurrence; we end up with a sum whose terms decrease faster than geometrically, so it's Θ of its largest term.

Space usage will be asymptotically the same since space usage is bounded above by time and below by the total size of the output, which are the same Θ.