Recursion
The trick is that each time a recursive function calls itself, it reduces the given problem into subproblems. The recursion call continues until it reaches a point where the subproblem can be solved without further recursion.
Reverse a string:
void printReverse(const char *str) {
if (!*str)
return;
printReverse(str + 1);
putchar(*str);
}
Fibonacci:
def fibonacci_recursive(n):
if n <= 1:
return n
else:
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
def fibonacci_tail_recursive(n, a=0, b=1):
if n == 0:
return a
elif n == 1:
return b
else:
return fibonacci_tail_recursive(n - 1, b, a + b)
Divide and Conquer. Beautiful!