Recursion is cute, no? After all, this is what every programmer learns in his early days while attempting (and failing at) the *Towers of Hanoi* problem. But this cuteness comes at a cost: overhead of making a lot of function calls.

Consider this simple Java program that produces the first 100 members of the Fibonacci series:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public class Fib1 { public static long F(int N) { if (N == 0) return 0; if (N == 1) return 1; return F(N-1) + F(N-2); } public static void main(String[] args) { for (int N = 0; N < 100; N++) { StdOut.println(N + " " + F(N)); } } } |

When I run it on my SSD-enhanced, Intel i5-powered laptop, the computation time starts hitting several seconds even as the 44th member is being printed. Interesting . . . I’m now intrigued about *exactly how many* function calls are being made. So let’s tweak this program a little and add a static variable to keep the count:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public class Fib1 { static long total_calls = 0; public static long F(int N) { Fib1.total_calls++; if (N == 0) return 0; if (N == 1) return 1; return F(N-1) + F(N-2); } public static void main(String[] args) { for (int N = 0; N < 100; N++) { Fib1.total_calls = 0; StdOut.println(N + " " + F(N) + ". Total calls: " + total_calls); } } } |

This run reveals something startling:

As you can see, the function exhibits *insane* growth as soon as it nears N=40. At N=44, this “cute” recursive function is making more than **2 billion function calls!**

That’s scary. Now let’s convert it into an iterative computation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
public class Fib2 { static long total_calls = 0; public static long F(int N) { if ((N == 0) || (N == 1)) { Fib2.total_calls++; return N; } long num1 = 0; long num2 = 1; for (int n = 0; n < N; n++) { Fib2.total_calls++; long temp = num2; num2 = num1 + num2; num1 = temp; } return num2; } public static void main(String[] args) { for (int N = 0; N < 100; N++) { Fib1.total_calls = 0; StdOut.println(N + " " + F(N) + ". Total calls: " + Fib2.total_calls); } } } |

And the resulting growth graph:

Look like a quadratic growth curve. As you can see, for N=40, we now have to make only 821 calls as opposed to 2 billion+ form before. Quite an improvement!

Moral of the story: Go easy on recursion, people!