Recursion

1. What is recursion
2. Three rules of recursion
3. Examples
   • Fibonacci
   • Factorial
4. Additional Resources

What is recursion?

Recursion is a method of solving problems based on divide and conquer.It is a very elegant way to write solutions to problems that would be pretty inefficient in an iterative solution ( using loops ). A recursive function is basically a function that calls itself on a problem that is somehow smaller or more simplified than the original problem .
For example see the function sum of list

#Iterative Solution--->
1)def listSum( list ) :
2)  sum =  0
3)  for i in list :
4)     sum += i 
5)  return sum

1)def listSum( list ) :
2)  if len( list ) == 1 :
3)    return list[0]
4)  else :
5)  return list[0] + listSum(list[1:])

In the iterative solution we go through each item in the list and keep adding it to the sum variable . But the same can be solved using a recursive solution . First, in line 2 we check for the base case,that is if the list is one element long and we return the element if the condition is satisfied. Then one line 5, we apply the recursive logic . The logic is that the sum of the list is the sum of the first item in the list and the listSum() of rest of the list .

Three rules of recursion

1. A recursive algorithm MUST have a base case
   For example in our recursive list sum example , We check for the base case by instructing it to return the only element present in the list if the list's length is 1.
2. A recursive algorithm must change its state in some way and move towards the base case .
   We move towards the base case in listSum by dividing the list on every recursive call until we reach the base case
3. A recursive algorithm must call itself recursively .
   Like in our example we repeatedly call listSum on a progressively smaller list.

< name="examples">Examples

1. Fibonacci
   fibonacci series is a special series where the value of n^th term is the sum of (n-1)^th term and (n-2)^th term. Here's how we will implement the program to find the value of the fibonacci number at n^th term.

   
   def fib(abs(n)):
       if n <= 2:
           return 1
       else:
           return fib(n-1) + fib(n-2)
   
   



2. Factorial
   A factorial of a number is expressed as n! and it is computed as the product of the number and all other integers below it . For example 4 Factorial(4!) will be 24 as it is 4 * 3* 2 * 1 = 24.
   So,now we can compute the factorial of a number recursively.
   

def factorial(abs(n)) : if n <= 1 : return 1 else : return n * factorial(n - 1)

Here are some other additional resources

1. Topcoder
2. GeekforGeeks