Algorithm Recursive/Recursion Method

 Recursion method by definitions is a way of solving a problem by having a function calling itself and make the problems become smaller and easier to find solutions.

Why We Need Recursion?

1. Recursion can break big problems into smaller ones and easy to use

2. Prominent usage of recursion in data structures like trees and graphs

3. Used in many algorithm (divide and conquer, greedy and dynamic programming)

How it works?

1. The method call it self

2. There's end conditions to interrupt loop

3. In stack Memory using FILO.

Recursive Vs Iterative Solutions?

Stack memory require?
    Recursive: Yes
    Iterative: No

Time Efficient?
    Recursive: No
    Iterative: Yes

Easy To Code?
    Recursive: Yes
    Iterative: No

When To Use Recursion:

1. When conditions breakdown to similar small sub problems meet

2. When Fine with extra overhead

3. When need quick working solutions

4. When traverse a tree

5. When use memorization in recursion

Method to do Recursion:

1. Identify the Recursive Flow

    Example:

    Factorial Problems: 5! = 5*4*3*2*1 => n * (n-1) * (n-2) * (n-3) ... *2 * 1 
    Define Formula: n! = n * f(n-1)

2. Determine Stop Conditions

    if n in [0,1]:

3. Handle Unintentional case - the constraint

    assert n >= 0 and int(n) == n 

Example:

Example with Factorial Problems (5! = 5*4*3*2*1):

import sys

sys.setrecursionlimit(100)

def factorial(n):

    # Step 3. Handle Unintentional case. The number must Positive Int Only

    assert n >= 0 and int(n) == n

    # step 2. Determine Stop Conditions

    if n in [0,1]:

        return 1

    else:

        # step 1. Identify the Recursive Flow

        return n * factorial(n-1)

print(factorial(-3))

Example with Fibonaci Problems (0, 1, 1, 2, 3, 5, 8, ...):

import sys

sys.setrecursionlimit(100)

def fibonacci(n):

    # Step 3. Handle Unintentional case. The number must Positive Int Only

    assert n >= 0 and int(n) == n

    # step 2. Determine Stop Conditions. if 0 or 1

    if n in [0,1]:

        return n

    else:

        # step 1. Identify the Recursive Flow

        # 0,1,1,2,3,5,8:

        # n2 = 0 + 1 ; n3 = 1 + 1 ; n4 = 2 + 1 ; n5 = 3 + 2 ; n6 = 5 + 3

        #  f = f(n - 1) + f (n - 2)

        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(5))

Example with Sum Of Digits ( 108 = 10 +8 ;  56 = 5 + 6):

Read More