title: Complexity of a recursive function that counts paths in graph
body: <p>I have found a function for a directed graph, which for vertices ‘u’ and ‘v’ in it, it counts all possible walks from ‘u’ to ‘v’ with exactly k edges on the walk.
  The code and the algorithm are from <a href="http://www.geeksforgeeks.org/count-possible-paths-source-destination-exactly-k-edges/" rel="nofollow">here</a>. So,</p>
  
  <pre><code>// C++ program to count walks from u to v with exactly k edges
  #include &lt;iostream&gt;
  using namespace std;
  
  // Number of vertices in the graph
  #define V 4
  
  // A naive recursive function to count walks from u to v with k edges
  int countwalks(int graph[][V], int u, int v, int k)
  {
     // Base cases
     if (k == 0 &amp;&amp; u == v)      return 1;
     if (k == 1 &amp;&amp; graph[u][v]) return 1;
     if (k &lt;= 0)                return 0;
  
     // Initialize result
     int count = 0;
  
     // Go to all adjacents of u and recur
     for (int i = 0; i &lt; V; i++)
         if (graph[u][i])  // Check if is adjacent of u
             count += countwalks(graph, i, v, k-1);
  
     return count;
  }
  </code></pre>
  
  <p>I am trying to find and prove the complexity of this algorithm. According to the post:</p>
  
  <blockquote>
    <p>"The worst case time complexity of the above function is O(V^k) where V
    is the number of vertices in the given graph. We can simply analyze
    the time complexity by drawing recursion tree. The worst occurs for a
    complete graph. In worst case, every internal node of recursion tree
    would have exactly n children."</p>
  </blockquote>
  
  <p>But, I cannot find the recursion that leads to a tree I can analyze in order to prove that this algorithm is <code>O(V^k)</code>. Also, I suppose that the best case is <code>Theta(1)</code>. Is that true? What about the average case?</p>