Đang chuẩn bị liên kết để tải về tài liệu:
Data structures and Algorithms: Recursion

Data structures and Algorithms: Recursion presents What is recursion? Outline of a Recursive Function, Recursive Factorial Method, Fibonacci sequence, Design a Recursive Algorithm, Euclid's Algorithm, Multiple recursion. | Recursion Data structures and Algorithms What is recursion? A way of thinking about problems. A method for solving problems. Related to mathematical induction. int f () { . f(); . } In programming: a function calls itself direct recursion a function calls its invoker indirect recursion Recursion int f () { . g(); . } int g () { . f(); . } 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)! 0! = 1 return 4*6 = 24 call final answer recursiveFactorial(4) call 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) + .