Recursion Data structures and Algorithms What is recursion? Outline of a Recursive Function, Recursive Factorial Method, Fibonacci sequence, Tracing fib, Design a Recursive Algorithm, Euclid's Algorithm. | Recursion Data structures and Algorithms What is recursion? a function calls itself direct recursion a function calls its invoker indirect recursion Recursion 2 Outline of a Recursive Function base case recursive case if (answer is known) provide the answer else make a recursive call to solve a smaller version of the same problem Recursion 3 Recursive Factorial Method n! = n * (n-1) * (n-2) * * 3 * 2 * 1 n! = n * (n-1)! return 4*6 = 24 call 0! = 1 recursiveFactorial(4) call final answer return 3*2 = 6 recursiveFactorial(3) return 2*1 = 2 call Algorithm recursiveFactorial(n) if n==0 then return 1 else return n * recursiveFactorial(n-1) recursiveFactorial(2) call return 1*1 = 1 recursiveFactorial(1) call return 1 recursiveFactorial(0) Recursion 4 Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, . 1 for n == 1 fib(n) = 1 for n == 2 fib(n-2) + fib(n-1) for n > 2 Algorithm fib(n) if n<=2 then return 1 else return fib(n-2) + .
