Recursion is a method that programmers use to make their code short and clear, and it happens when the function calls itself. There is always a base case to stop infinite recursion, which is the simplest case that can be solved easily. Other than base case, there are some recursive calls and relations between them and a return statement which is generated with the results of the recursive calls. Usually, divide and conquer algorithms, such as quick sort, merge sort, and binary search are implemented using recursion, because recursion divides a problem into smaller subproblems, solves them with recursion (which will divide them again until base case) and combines their results to solve the original problem. The first recursive algorithm I wrote was finding Nth fibonacci number. Fibonacci numbers are generate with formula: F[i] = F[i-1] + F[i-2]. Base cases are F[0] = 0, F[1] = 1. So the python code for this algorithm would be:
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n-1) + fib(n-2)
Now, in these simple problems the length of recursive method isn't much different from using a list and loop, but in general it is much simpler to write recursion because it works from top to bottom, and you know the top. In contrast, if you use loops and dynamic programming although it is very fast, it is hard to think from base cases to top. Also, we can use memorization to improve time efficiency of recursion.
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n-1) + fib(n-2)
Now, in these simple problems the length of recursive method isn't much different from using a list and loop, but in general it is much simpler to write recursion because it works from top to bottom, and you know the top. In contrast, if you use loops and dynamic programming although it is very fast, it is hard to think from base cases to top. Also, we can use memorization to improve time efficiency of recursion.
