Recursion in Python

What is Recursion?
Recursion is a technique where a function calls itself in order to solve a
problem. It breaks a problem into smaller subproblems and solves them
recursively.
Key Components of Recursion:
❖​ Base Case: A condition that stops the recursion to prevent infinite
loops.
❖​ Recursive Case: The function calls itself with a modified argument,
moving towards the base case.
Program 1:
def welcome():
print("Hello Recursion....")
welcome()
welcome()
Output:
Hello Recursion....
Hello Recursion....
………………………….. 1000 times​​ ​ ​ ​ ​ ​ ​
Program 2:
import sys
print(sys.getrecursionlimit())
Output:
1000
Program 3:
import sys
sys.setrecursionlimit(2000)
print(sys.getrecursionlimit())
i=0
def welcome():
global i
i=i+1
print("Hello Recursion....",i)
welcome()
welcome()
Output:
Hello Recursion.... 1
Hello Recursion.... 2
…………………………………………………….
Hello Recursion.... 1970
Hello Recursion.... 1971
Program 4: calculate factorial using iterative
def factorial(n):
result = 1
for i in range(1, n + 1):
result= result*i
return result

print("Factorial of 5 using loop:", factorial(5))

Output:
Factorial of 5 using loop: 120
Program 5: calculate factorial using iterative
def factorial(n):
if n == 0: # Base case
return 1
return n * factorial(n - 1) # Recursive case

print("Factorial of 5 using recursion:", factorial(5))

Output:
Factorial of 5 using recursion: 120

Program 6: Print fibonacci series up to a specific term using

Iterative approach.
def fibonacci_iterative(n):
a, b = 0, 1
for _ in range(n):
print(a, end=" ")
a, b = b, a + b

# Example usage
num_terms = int(input("Enter the number of terms: "))
fibonacci_iterative(num_terms)
Output:
Enter the number of terms: 5
0 1 1 2 3
Program 7: Print fibonacci series up to a specific term using
recursion approach.
def fibonacci(n):
if n <= 0:
return "Input should be a positive integer"
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)

# Print Fibonacci series up to n terms

def print_fibonacci_series(n):
for i in range(1, n + 1):
print(fibonacci(i), end=" ")

# Example usage
num_terms = int(input("Enter the number of terms: "))
print_fibonacci_series(num_terms)
Output:
Enter the number of terms: 5
0 1 1 2 3
Program:
write a code where user will give an integer number where the
program will display in descending order
a)​Using Iterative method
# Get user input
n = int(input("Enter an integer: "))

# Display numbers in descending order

for i in range(n, 0, -1):
print(i)
Output:
Enter an integer: 5
5
4
3
2
1
b)​ Using recursion
def descending(n):
if n <= 0:
return # Base case: Stop when n reaches 0
print(n) # Print the current number
descending(n - 1) # Recursive call with n-1

# Get user input

num = int(input("Enter an integer: "))

# Call the recursive function

descending(num)
Output:
Enter an integer: 5
5
4
3
2
1
 Searching
1.​ Linear Search

Linear Search is the simplest searching algorithm. It works by checking

each element in a list one by one until the target element is found or the
list ends.

How Linear Search Works?

1.​ Start from the first element of the array.

2.​ Compare each element with the target value.
3.​ If a match is found, return the index of the element.
4.​ If the target is not found, return -1 (indicating the element is not
present).

import numpy as np
np.random.seed(11)
values = np.random.randint(10, 91, 10)
values
Output:
array([35, 73, 90, 65, 23, 86, 43, 81, 34, 58])
def linear_search(data, search_key):
for index, value in enumerate(values):
if value == search_key:
return index
return -1
linear_search(values, 23)
Output:
4
Big O Comparison
1.​ Best Case (O(1)):

If the target element is at the beginning of the list, the search completes
in just one comparison.
Example: Searching for 5 in [5, 10, 15, 20] → Found in 1 step.
2.​ Worst Case (O(n)):

If the target element is at the end of the list or not present, the algorithm
must check all n elements.
Example: Searching for 20 in [5, 10, 15, 20] → 4 comparisons.
 3.​ Average Case (O(n)):

On average, the search will find the target in about n/2 comparisons.
However, since we use Big O notation to represent the worst-case
scenario for scalability, we simplify O(n/2) to O(n)
2. Binary Search
Binary Search is an efficient searching algorithm used on sorted lists. It
works by repeatedly dividing the search space in half until the target
element is found or the list is exhausted.

How Binary Search Works?

1.​ Start with a sorted array.

2.​ Find the middle element.
3.​ Compare it with the target:
○​ If the middle element is equal to the target → return its
index.
○​ If the target is smaller, search in the left half.
○​ If the target is greater, search in the right half.
4.​ Repeat this process until the target is found or the list is empty.

import numpy as np
np.random.seed(11)
data = np.random.randint(10, 91, 15)
data
Output:
array([35, 73, 90, 65, 23, 86, 43, 81, 34, 58, 42, 55, 14, 44, 22])
data.sort()
print(data)
Output:
[14 22 23 34 35 42 43 44 55 58 65 73 81 86 90]
def remaining_elements(data, low, high):
"""Display remaining elements of the binary search."""
return ' ' * low + ' '.join(str(s) for s in data[low:high + 1])

def binary_search(data, key):

"""Perform binary search of data looking for key."""
low = 0 # low end of search area
high = len(data) - 1 # high end of search area
 middle = (low + high + 1) // 2 # middle element index
location = -1 # return value -1 if not found

# loop to search for element

while low <= high and location == -1:
# print remaining elements of array
print(remaining_elements(data, low, high))
print(' ' * middle,end='') # output spaces for alignment 3 space
print(' * ') # indicate current middle
# if the element is found at the middle
if key == data[middle]:
location = middle # location is the current middle
elif key < data[middle]: # middle element is too high
high = middle - 1 # eliminate the higher half
else: # middle element is too low
low = middle + 1 # eliminate the lower half
middle = (low + high + 1) // 2 # recalculate the middle
return location # return location of search key

search_key = int(input('Enter an integer value (-1 to quit): '))

while search_key != -1:
location = binary_search(data, search_key) # perform search
if location == -1: # not found
print(f'{search_key} was not found\n')
else:
print(f'{search_key} found in position {location}\n')
search_key = int(input('Enter an integer value (-1 to quit): '))

Output:
Enter an integer value (-1 to quit): 34
14 22 23 34 35 42 43 44 55 58 65 73 81 86 90
*
14 22 23 34 35 42 43
*
34 found in position 3
Enter an integer value (-1 to quit): 55
14 22 23 34 35 42 43 44 55 58 65 73 81 86 90
*
55 58 65 73 81 86 90
*
55 58 65
*
55
*
55 found in position 8
Time Complexity:

1. Best Case (O(1))

●​ If the target element is found in the first middle check, the search
completes in O(1) time.
●​ Example: Searching for 6 in [2, 4, 6, 8, 10] → Found
immediately.

2. Worst Case (O(log n))

●​ In the worst case, the search keeps reducing the array size by half
until one element remains.
●​ If we start with n elements, the number of elements left after each
step is:
○​ 1st step → n/2
○​ 2nd step → n/4
○​ 3rd step → n/8
○​ …
○​ kth step → n / 2^k
 ●​ The search ends when only one element is left:​

3. Average Case (O(log n))

●​ Since binary search eliminates half of the search space at each step,
the expected number of steps remains around O(log n) in most
cases.
●​ This is true whether the element is found or not.

1. Selection Sort

Selection Sort is a simple and efficient comparison-based sorting

algorithm. It works by repeatedly finding the smallest (or largest)
element from the unsorted part of the array and swapping it with the
first unsorted element.

Working Principle

1.​ Start from the first element and assume it is the smallest.
2.​ Compare it with the rest of the elements to find the actual smallest
element.
3.​ Swap the smallest element with the first element.
4.​ Move to the next position and repeat the process for the remaining
unsorted elements.

Continue until the entire array is sorted.

Time Complexity
 Case Time
Complexity

Best Case O(n²)

Worst O(n²)
Case

Average O(n²)
Case

arr = [64, 11, 12, 22, 25]

def selection_sort(arr):

n = len(arr)

for i in range(n - 1):

min_index = i

for j in range(i + 1, n):

if arr[j] < arr[min_index]:

min_index = j

arr[i], arr[min_index] = arr[min_index], arr[i]

print(f"Pass {i + 1}: {arr}")

print("Original array:", arr)

selection_sort(arr)

print("Sorted array:", arr)

Output:
Original array: [64, 11, 12, 22, 25]
Pass 1: [11, 64, 12, 22, 25]
Pass 2: [11, 12, 64, 22, 25]
Pass 3: [11, 12, 22, 64, 25]
Pass 4: [11, 12, 22, 25, 64]
Sorted array: [11, 12, 22, 25, 64]

2. Insertion Sort:
Insertion Sort is a simple and efficient sorting algorithm that builds the
sorted list one element at a time by taking each element and inserting it
into its correct position.

Steps of Insertion Sort:

1.​ Start with the second element (index 1) and compare it with the
elements before it.
2.​ Shift larger elements one position to the right.
3.​ Insert the current element in its correct position.
4.​ Repeat for all elements until the array is sorted.

Example:

Unsorted Array: [64, 25, 12, 22, 11]

●​ Pass 1: [25, 64, 12, 22, 11]

●​ Pass 2: [12, 25, 64, 22, 11]
●​ Pass 3: [12, 22, 25, 64, 11]
●​ Pass 4: [11, 12, 22, 25, 64] (Sorted)

Time Complexity Analysis:

●​ Best Case (Already Sorted): O(n)O(n)O(n)

●​ Worst Case (Reverse Sorted): O(n2)O(n^2)O(n2)
●​ Average Case: O(n2)O(n^2)O(n2)

Program:

arr = [64, 11, 12, 22, 25]

def insertion_sort(arr):

n = len(arr)

for i in range(1, n):

key = arr[i]

j=i-1
 while j >= 0 and key < arr[j]:

arr[j + 1] = arr[j]

j -= 1

arr[j + 1] = key

print(f"Pass {i}: {arr}")

print("Original array:", arr)

insertion_sort(arr)

print("Sorted array:", arr)

Output:
Original array: [64, 11, 12, 22, 25]
Pass 1: [11, 64, 12, 22, 25]
Pass 2: [11, 12, 64, 22, 25]
Pass 3: [11, 12, 22, 64, 25]
Pass 4: [11, 12, 22, 25, 64]
Sorted array: [11, 12, 22, 25, 64]

3. Merge Sort:
What is Merge Sort?

Merge Sort is a divide and conquer sorting algorithm that recursively

splits an array into smaller subarrays, sorts them, and merges them back
together in a sorted order.

Steps of Merge Sort Algorithm:

1.​ Divide: Split the array into two halves until each subarray contains
a single element.
2.​ Conquer: Recursively sort each half.
3.​ Merge: Merge the sorted halves back into a single sorted array.

Example of Merge Sort:

Unsorted Array: [38, 27, 43, 3, 9, 82, 10]

1.​ Divide:
○​ [38, 27, 43, 3] and [9, 82, 10]
○​ [38, 27], [43, 3] and [9, 82], [10]
○​ [38], [27], [43], [3], [9], [82], [10]
2.​ Merge and Sort:
○​ [27, 38], [3, 43], [9, 82], [10]
○​ [3, 27, 38, 43], [9, 10, 82]
 ○​ [3, 9, 10, 27, 38, 43, 82] (Final sorted array)

Program:
arr = [64, 11, 12, 22, 25]
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]

merge_sort(left_half)
merge_sort(right_half)

i=j=k=0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1

while i < len(left_half):

arr[k] = left_half[i]
i += 1
k += 1

while j < len(right_half):

arr[k] = right_half[j]
j += 1
k += 1
 print(f"Merging: {arr}")
print("Original array:", arr)
merge_sort(arr)
print("Sorted array:", arr)

Output:

Original array: [64, 11, 12, 22, 25]

Merging: [11, 64]

Merging: [22, 25]

Merging: [12, 22, 25]

Merging: [11, 12, 22, 25, 64]

Sorted array: [11, 12, 22, 25, 64]