A. recursive algorithm
1.
-Reduce a problem to a simpler (or smaller) version of the same problem, plus some simple computations
• Recursive step
-Keep reducing until reach a simple case that can be solved directly
• Base case
ex: a * b = a; if b = 1 (Base case)
a * b = a + a * (b-1); otherwise (Recursive case)
2. Euclidean algorithm
The greatest common divisor of two positive integers is the largest integer that divides each of them without remainder.
suppose that a and b are two positive integers:
If b = 0, then the answer is a
Otherwise, gcd(a, b) is the same as gcd(b, a % b)
3. other instances for recursive: Fibonacci numbers/ tower of Hanoi
4. recursion on strings: #palindrome
#认真思考 base case： L5P8/P9
