Home on the Range of Lists

Pyth, 13 bytes

?hu]+HG_UQYQY

Try it here.

                 Implicit:
                 Q = eval(input())
                 Y = []
?           QY   If Q = 0, print Y
 h               else, print the first element of
  u     _UQY     the reduce, where Y is the initial value, over the list
                 reversed(range(Q))
   ]+HG          The reduce function: The list containing H prepended onto G.
                 The new number is inserted into the accumulated list,
                 then the resultant list is wrapped in another list.

APL (13 18)

Assuming ⎕IO=0:

f←{×⍵:⊃,∘⊂∘,/⍳⍵⋄⍬}

Explanation:

  • ×⍵: if is positive,
    • ,∘⊂∘,: join the left operand to the enclose of the right operand (i.e. x ,∘⊂∘, y = [x, [y]])
    • /: reduce
    • ⍳⍵: the numbers 0..⍵-1
    • : disclose the result
  • : otherwise
    • : return the empty list
    • (this is necessary because / fails on , and ⍳0 gives the empty list.)

Addendum:

This function returns a nested array. However, it is a bit hard to tell this from APL's default output. It separates array items by spaces, so you can only tell nesting by double spaces. Here is a function that will take a nested array, and return a string, formatting the nested array in Python style (i.e. [a,[b,[c,...]]]).

arrfmt←{0=≡⍵:⍕⍵ ⋄ '[',(1↓∊',',¨∇¨⍵),']'}

Haskell, 67 bytes

data L=E|I Int|L[L] 
1#m=L[I$m-1]
n#m=L[I$m-n,(n-1)#m]
p 0=E
p n=n#n

In Haskell all elements of a list have to be of the same type, so I cannot mix integers with list of integers and I have to define a custom list type L. The helper function # recursively constructs the required list. The main function p checks for the empty list and calls # otherwise.

As new data types cannot be printed by default (the rules allow just to return the list), I add some more code for demonstration purpose:

data L=E|I Int|L[L] deriving Show

Now:

-- mapM_ (print . p) [0..5]
E
L [I 0]
L [I 0,L [I 1]]
L [I 0,L [I 1,L [I 2]]]
L [I 0,L [I 1,L [I 2,L [I 3]]]]
L [I 0,L [I 1,L [I 2,L [I 3,L [I 4]]]]]