At every level of recursion a fibo(n) is making calls to fibo(n/2) and fibo(n/2 + 1) So the number of digits of the result of each recursion is half as many as the caller is calculating. 500000, 250000, 125000, 62500, 31250....etc. They get small pretty fast. That's not very precise. Here is a list...