title: Time complexity of doubly recursive function
body: <p>So this is the code:</p>
  
  <pre><code>int test ( int n) 
  { 
     if (n ≤2) return 1; 
     else return test(n-2) * test(n-2); 
  } 
  </code></pre>
  
  <p>I'm not confident in how to reason about this recursive function. I tried mapping the N value to the recursion depth like so:</p>
  
  <pre><code>N = 2 -&gt; 0 recursions
  N = 4 -&gt; 2
  N = 8 -&gt; 14
  </code></pre>
  
  <p>But to be honest I'm not sure this gets me anywhere (and just thinking about test(16) hurts my head.</p>