Time complexity of DFS and recurrence relation
For an implicit graph  the recurrence can be written as follows:

Let $b$ be the number of branches of every node (assumed to be constant)

let $d$ the depth of the graph

For depth 1 there are $b$ branches:

$T(b,1) = b$

For the next levels it can be written as

$T(b,d) = b + b*T(b,d-1)$

where $b$ are the nodes at this level, and are the $b*T(b,d-1)$ nodes at next level.

If you substitute the definition for $T(b,d-1)$ you get 

$b * (1 + b*(1+T(b,d-2)) = b + b^2(1+T(b,d-2))$

If you further substitute the definition of $T(b,d-2)$ you get

$b + b^2(1+b+b*T(b,d-3)) = b + b^2 + b^3 + b^3*T(b,d-3)$

If you continue to expand you get

$T(b,d) =  b + b^2 +b^3 +... + b^{d-1}*T(b,1)$

Since we know that $T(b,1) = b$, we can substitute

$T(b,d) =  b + b^2 +b^3 +... + b^{d-1}*b$

Thus 

$T(b,d) =  b + b^2 +b^3 +... + b^d$

Using Big-O Notation. $O(b^d)$

For explicit graphs with $V$ vertex and $E$ edges

We assume you have an adjacent list. That is for every $V$ you have a list of adjacent edges. You can think of a Table of $E$ edges (columns) x $V$ vertex (rows).

We can write our recurrent relation based on the navigation of that table.

$T(V,E) = 1 + e_0 + T(V-e_0,E-e_0)$

We count $1$ for visiting the first row, and $e_0$ for the number of edges adjacent to that first vertex.  For the next rows we use the recurrent relation except this time we have $V-e_0$ vertex and $E-e_0$ edges to visit.

If we substitute our definition for the 3rd. element in our relation we get:

$T(V,E) =  1 + e_0 + 1 + e_1 + T(V-e_1,E-e_1)$

if you keep expanding you get

$T(V,E) =  1 + 1 + .. + 1 + e_0 +e_1 + .. + e_V$

1 for every row visited and a certain number of edges for a given vertex.  In total the number of edges is $E =e_0 + e_1 + .. e_V$.

$T(V,E) =  V + E$

in Big-O Notation $O(V+E)$.