Recursive Functions and Iteration Comparison

Chapter 1.3 Recursion A recursive function is a function that calls itself. unsigned long Factorial (int n) { if (n<=1) return 1; else return n*Factorial(n-1); }

Chapter 1.3 Recursion Two key points of a recursive function: 1. It needs to have a way out there should be a case (condition) that the function does not call itself. We call this base case. If no way out, the program will eventually crash for running out of memory (each function call uses some memory, which is called activation record). 2. In the case when the function calls itself, it must make progress (through function parameter) towards the base case. unsigned long Factorial (int n) { if (n<=1) return 1; else return n*Factorial(n-1); } Base case, no more recursive call Make progress when the function calls itself Factorial(n) calls Factorial(n-1). (the parameter is 1 smaller)

Recursion and loop Many tasks can be done with recursion can also be done by iteration oiteration involves a loop, but not recursive calls When using a loop, one should always allow a "way out" (avoid infinite looping). Every loop iteration must make progress toward the end of the loop.

Recursion and loop Factorial(n) can be defined as n * (n-1) * (n-2) * ... * 1. The factorial function can also be defined as: o Factorial(1) = 1 o Factorial(n) = n * Factorial(n-1) Factorial(3) = 3 * Factorial(2) Factorial(2) = 2 * Factorial(1) Factorial(1) = 1 Factorial(3) => 3 * Factorial(2) => 3 * 2 * Factorial(1) => 3 * 2 * 1

Recursion and loop Factorial(n) can be defined as n * (n-1) * (n-2) * ... * 1. Factorial(n) can be defined as n * Factorial(n-1) with Factorial(1) = 1. unsigned long Factorial (int n) { unsigned long f = 1; for (int i=n; i>=1; i--) f*=i; return f; } unsigned long Factorial (int n) { if (n<=1) return 1; else return n*Factorial(n-1); }

More recursion What happens with the following recursive functions? unsigned long Factorial (int n) { if (n<=1) return 1; else return n*Factorial(n+1); } unsigned long Factorial (int n) { if (n<=1) return 1; else return n*Factorial(n); } for(int i=n; i>=1; i++) f *= i; In both programs, the recursive calls do not make progress towards the base case (n <=1).

Recursion What happens with this program? Int bad (int n) { if (n== 0) return 0; else return bad(n/3+1) + n-1; } Make sure that the recursive function makes progress in all situations!

Recursion and induction The pattern for recursion is very similar to induction o both have the base cases o Recursive case corresponds to the induction case o The thinking process for recursion and induction is actually the same. Assume the recursive calls (which solve smaller problems) work, the combined logic in the recursive case must solve the original problem). unsigned long Factorial (int n) { if (n<=1) return 1; else return n*Factorial(n-1); } Assume that Factorial(n-1) computes (n-1)!, n*Factorial(n-1) computes n!

Recursive function Basic rules to keep in mind when writing a recursive function: 1. Base cases: a recursive function should always have base cases that do not make recursive calls 2. Making progress: for the cases that make recursive calls, all recursive calls must make progress toward base case. 3. Solving the original problem Assume that all recursive calls work, the combined logic in the recursive case must solve the original problem.

Another example: fibonnaci numbers ???1= 1;???2= 1; ????= ???? 1+ ???? 2 int Fib (int n) { if (n<=1) return 1; else if (n==2) return 1; else return Fib(n-1) + Fib(n-2); }

One more example: Sum of all elements in an array int sum(A, n) /* find the A[0] + A[1] + A[2] + + A[n-1] */ If sum(A, n-1) finds the sum of n-1 elements (A[0] + A[1] + A[2] + + A[n- 2]), how to find the sum of n elements (sum(A, n))?