05AB1E, 8 bytes

Code:

¾)IF·D>« 

Explanation:

¾ # Constant for 0. ) # Wrap it up into an array. IF # Do the following input times. · # Double every element. D # Duplicate it. > # Increment by 1. « # Concatenate the first array. 

Uses the CP-1252 encoding. Try it online!.

J, 15 bytes

2|."1&.#:@i.@^] 

Uses straight-forward binary conversion and reversal.

For 20 bytes,

([:(,>:)+:@$:@<:)^:* 

Uses the recursive, double and increment method.

Usage

 f =: 2|."1&.#:@i.@^] g =: ([:(,>:)+:@$:@<:)^:* (f,:g) 0 0 0 (f,:g) 2 0 2 1 3 0 2 1 3 (f,:g) 3 0 4 2 6 1 5 3 7 0 4 2 6 1 5 3 7 (f,:g) 4 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 

Explanation

2|."1&.#:@i.@^] Input: n ] Get n 2 ^ Find 2^n i.@ Get the range [0, 1, ..., 2^n-1] |."1&.#:@ Convert each value to binary using #: Then reverse each value using |."1 Then convert back to decimal from binary using the inverse of #: which is obtained from &. Return those values ([:(,>:)+:@$:@<:)^:* Input: n * Get the sign of n, either 0 if 0 or else 1 ( )^: Execute either 0 or 1 times When given 0, it executes 0 times on input 0 meaning that it returns a list [0] <: Decrement n to get n-1 $:@ Call recursively on n-1 +:@ Double each value in the recursive result [:( ) Modify the double result >: Increment each value in it , Join the doubled with the incremented result and return 

Octave, 37 bytes

@(n)bin2dec(fliplr(dec2bin(0:2^n-1))) 

Creates an anonymous function named ans that can simply be called with ans(n).

Online Demo

MATL, 1312109 8 bytes

0i:"EtQh 

Try it Online

Explanation

0 % Push number literal 0 to the stack i:" % Loop n times E % Multiply by two t % Duplicate Q % Add one h % Horizontally concatenate the result % Implicit end of loop, and implicitly display the result 

For the sake of completeness, here was my old answer using the non-recursive approach (9 bytes).

W:qB2&PXB 

Try it Online

Explanation

W % Compute 2 to the power% ofImplicitly thegrab input (n) and compute 2^n : % Create an array from [1...2^n] q % Subtract 1 to get [0...(2^n - 1)] B % Convert to binary where each row is the binary representation of a number 2&P % Flip this 2D array of binary numbers along the second dimension XB % Convert binary back to decimal % Implicitly display the result 

Pyth - 11 bytes

ushMByMGQ]0 

Test Suite.

Javascript ES6, 6553 51 bytes

f=(n,m=1)=>n?[...n=f(n-1,m+m),...n.map(i=>i+m)]:[0] 

Uses the recursive double-increment-concat algorithm.

Example runs:

f(0) => [0] f(1) => [0, 1] f(2) => [0, 2, 1, 3] f(4) => [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] 

Python 2, 5655 54 bytes

f=lambda n:[0][n:]or[i+j*2for i in 0,1for j in f(n-1)] 

Test it on Ideone.

Thanks to @xnor for golfing off 1 byte!

Java, 422 419 bytes:

import java.util.*;class A{static int[]P(int n){int[]U=new int[(int)Math.pow(2,n)];for(int i=0;i<U.length;i++){String Q=new String(Integer.toBinaryString(i));if(Q.length()<n){Q=new String(new char[n-Q.length()]).replace("\0","0")+Q;}U[i]=Integer.parseInt(new StringBuilder(Q).reverse().toString(),2);}return U;}public static void main(String[]a){System.out.print(Arrays.toString(P(new Scanner(System.in).nextInt())));}} 

Well, I finally learned Java for my second programming language, so I wanted to use my new skills to complete a simple challenge, and although it turned out very long, I am not disappointed. I am just glad I was able to complete a simple challenge in Java.

Try It Online! (Ideone)

Mathematica, 56 33 bytes

Byte count assumes an ISO 8859-1 encoded source.

±0={0};±x_:=Join[y=±(x-1)2,y+1] 

This uses the recursive definition to define a unary operator ±.

Jelly, 7 bytes

Ḥµ;‘ Ç¡ 

Try it online!

How it works

Ḥµ;‘ Helper link. Argument: A (array) Ḥ Double; yield 2A. µ Begin a new, monadic chain. Argument: 2A ‘ Increment; yield 2A + 1. ; Concatenate the results to both sides. Ç¡ Main link. No arguments. Implicit argument / initial return value: 0 ¡ Read an integer n from STDIN and do the following n times. Ç Call the helper link with the previous return value as argument. 

Julia, 23 22 bytes

!n=n>0&&[t=2*!~-n;t+1] 

Rather straightforward implementation of the process described in the challenge spec.

Try it online!

Python 3, 67 59 bytes

Thanks to @Dennis for -8 bytes

lambda n:[int(bin(i+2**n)[:1:-1],2)//2for i in range(2**n)] 

We may as well have a (modified) straightforward implementation in Python, even if this is quite long.

An anonymous function that takes input by argument and returns the bit-reversed permutation as a list.

How it works

lambda n Anonymous function with input n ...for i in range(2**n) Range from 0 to 2**n-1 bin(i+2**n)[:1:-1] Convert i+2**n to binary string, giving 1 more digit than needed, remove '0b' from start, and reverse int(...,2) Convert back to decimal ...//2 The binary representation of the decimal value has one trailing bit that is not required. This is removed by integer division by 2 :[...] Return as list 

Try it on Ideone

JavaScript (Firefox 30+), 46 bytes

n=>n?[for(x of[0,1])for(y of f(n-1))x+y+y]:[0] 

Port of @Dennis♦'s Python 2 solution.

Pyth, 8 bytes

iR2_M^U2 

Try it online: Demonstration or Test Suite

Explanation:

iR2_M^U2Q implicit Q (=input number) at the end ^U2Q generate all lists of zeros and ones of length Q in order _M reverse each list iR2 convert each list to a number