Programming - Recursion(6)

Administrivia

Practice Web Page - http://www.cs.tau.ac.il/~efif/courses/Programming_Fall_04

Recursive functions

• A recursive function is one that calls itself
• It must make the decision not to call itself again
  • Bottoming Out - popping addresses off the stack and returning to the previous functions. Eventually, the very first function in the chain terminates, and the program ends successfully.
• There is always an alternative non-recursive solution available too
  • normally involve the use of a loop
  • may lack the elegance of the recursive solution

Factorial

• A program that calculates the factorial of a number using recursion

  #include <stdio.h> int fact(int num) { if (num == 1) return 1; return num * fact(num - 1); } int main() { int num; printf("Enter a number: "); scanf("%d", &num); printf("The factorial is %d\n", fact(num)); return 0; }

• rfact.c

The power of a number

• double power(double val, unsigned pow) { if (pow == 0) /* pow(x, 0) returns 1 */ return 1.0; else return power(val, pow - 1) * val; }

• rpow.c

Fibonacci function

• /* Fibonacci value of a number */

  int fib(int num) { switch(num) { case 0: return(0); break; case 1: return(1); break; default: return(fib(num - 1) + fib(num - 2)); break; } }

• rfib.c
• Number of calls

  Input Value	No. of calls	Fibonacci
  0	1	0
  1	1	1
  2	3	1
  3	5	2
  4	9	3
  5	15	5
  6	25	8
  7	41	13
  8	67	21
  9	109	34
  10	177	55