Recursive function is very useful in many situations. However, in some cases it calculate the subproblem more than once which leads it to waste a lot of time. The nth fibonacci generator is a good example for this. I wrote this program to show how many function calls are called to get the nth fibonacci number. The program will iteratively ask for input (input n indicates you want the nth fibonacci number). and it will output the nth fibonacci number and how many function calls are called. Here are some sample results:
Input a number(-1 for exit): 5 The 5th fibonacci number is: 5 function called: 9 times
Input a number(-1 for exit): 10 The 10th fibonacci number is: 55 function called: 109 times
Input a number(-1 for exit): 20 The 20th fibonacci number is: 6765 function called: 13529 times