As others pointed out, analyzing recursion can get very hard very fast. Here is another example of such thing: http://rosettacode.org/wiki/Mutual_recursion http://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences
it is hard to compute an answer and a running time for these. This is due to these mutually-recursive functions having a "difficult form".
Anyhow, let's look at this easy example:
(declare funa funb)
(defn funa [n]
(if (= n 0)
(funb (dec n))))
(defn funb [n]
(if (= n 0)
(funa (dec n))))
Let's start by trying to compute
funa(m), m > 0:
funa(m) = funb(m - 1) = funa(m - 2) = ... funa(0) or funb(0) = 0 either way.
The run-time is:
R(funa(m)) = 1 + R(funb(m - 1)) = 2 + R(funa(m - 2)) = ... m + R(funa(0)) or m + R(funb(0)) = m + 1 steps either way
Now let's pick another, slightly more complicated example:
Inspired by http://planetmath.org/encyclopedia/MutualRecursion.html, which is a good read by itself, let's look at: """Fibonacci numbers can be interpreted via mutual recursion: F(0) = 1 and G(0) = 1 , with F(n + 1) = F(n) + G(n) and G(n + 1) = F(n)."""
So, what is the runtime of F? We will go the other way.
Well, R(F(0)) = 1 = F(0); R(G(0)) = 1 = G(0)
Now R(F(1)) = R(F(0)) + R(G(0)) = F(0) + G(0) = F(1)
It is not hard to see that R(F(m)) = F(m) - e.g. the number of function calls needed to compute a Fibonacci number at index i is equal to the value of a Fibonacci number at index i. This assumed that adding two numbers together is much faster than a function call. If this was not the case, then this would be true: R(F(1)) = R(F(0)) + 1 + R(G(0)), and the analysis of this would have been more complicated, possibly without an easy closed form solution.
The closed form for the Fibonacci sequence is not necessarily easy to reinvent, not to mention some more complicated examples.