title: How to write recurrence of any recursive function?
body: <p>I have seen many examples, but couldn't get the right procedure to write the recurrence of any recursive function. For example: If I see these functions, 
  how can I write an accurate recurrence? </p>
  
  <pre><code>void print (int n)
  {
  if (n&gt;0)
  {cout&lt;&lt; n&lt;&lt;endl;
  print(n-1);}
  }
  </code></pre>
  
  <p>and</p>
  
  <pre><code>int power (int x, int n)
  {
          If (n==0)
          return 1;
      else
          return x * power (x, n-1);
  }
  </code></pre>
  
  <p>and</p>
  
  <pre><code>Int fib (int n)
  {
  If (n==0 or n==1)
      return 1;
  else
      return fib(n-1) +fib (n-2);
  }
  </code></pre>
  
  <p>and</p>
  
  <pre><code>int numberofDigits(int n) {
    if ((-10 &lt; n) &amp;&amp; (n &lt; 10))
      return 1;
    else
      return 1 + numberofDigits(n/10);
  }
  </code></pre>
  
  <p>Those are all recursive functions. We can see, some of the functions like (fibonacci, factorial etc) functions have pre-described recurrences on the internet. </p>
  
  <p>But how to write a recurrence by ourselves?</p>