# 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):

Share: