Recursion

a method where the solution to a problem depends on smaller ones

A Mandelbrot Set

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). Recursive algorithms have two cases: a recursive case and base case. Any function that calls itself is recursive.

Examples of recursive functions:

1. Factorial: n! = n x (n -1) x (n-2) x … x 1
2. Fibonacci: 1,1,2,3,5,8 ,…
3. Multiplication (3 x 2): 3 + 3
4. Multiplication (2 x 3): 2 + 2 + 2
5. Summations from i = 1 to 5: 1 + 2 + 3 + 4 + 5
6. n² + (n-1) ^2 + (n-2)² + … + 1
7. 1 + 10 + 100 + 1000 + 10000 + …..
8. 1 + 1 + 1 + … + 1
9. 0 + 1 + 2 + 3 + … + n
10. func( 0 ) = 0 , func(n) = func(n-1) + n
11. A Mandelbrot Set

Recursion is useful for tasks that can be defined in terms of similar subtasks, for example search, sort , and traversal problems often have simple recursive solutions. At some point the function encounters a subtask that it can perform without calling itself.

• Directly recursive: method that calls itself
• Indirectly recursive: method that calls…