Last Updated : 13 Jul, 2022
Examples :
Input: arr = {
1,
4,
3,
-5,
-4,
8,
6
};
Output: min = -5, max = 8
Input: arr = {
1,
4,
45,
6,
10,
-8
};
Output: min = -8, max = 45- Get the array for which the minimum is to be found
- Recursively find the minimum according to the following:
- Recursively traverse the array from the end
- Base case: If the remaining array is of length 1, return the only present element i.e. arr[0]
if (n == 1)
return arr[0];- Recursive call: If the base case is not met, then call the function by passing the array of one size less from the end, i.e. from arr[0] to arr[n-1].
- Return statement: At each recursive call (except for the base case), return the minimum of the last element of the current array (i.e. arr[n-1]) and the element returned from the previous recursive call.
return min(arr[n - 1], recursive_function(arr, n - 1));-50
- Get the array for which the maximum is to be found
- Recursively find the maximum according to the following:
- Recursively traverse the array from the end
- Base case: If the remaining array is of length 1, return the only present element i.e. arr[0]
if (n == 1)
return arr[0];-50
45
This is a recursive implementation of min:
l=[5, 3, 9, 10, 8, 2, 7]
def find_min(l,current_minimum = None):
if not l:
return current_minimum
candidate=l.pop()
if current_minimum==None or candidate<current_minimum: return find_min(l,candidate) return find_min(l,current_minimum) print find_min(l)>>>
2>>>
import random
>>>
arr = [random.randint(0, 8) for r in xrange(10)] >>>
arr[8, 2, 5, 1, 2, 4, 0, 3, 1, 1] >>>
def func(arr):
if len(arr) == 1:
return arr[0]
else:
return min(arr[0], func(arr[1: ]))
>>>
f(arr)
0This answer uses an accumulator to store the min value throughout the recursions.
list = [5, 3, 9, 10, 8, 2, 7]
def min_list(list, min = None):
if len(list) < 1:
return min
return min_list(list[1: ], list[0]
if min is None or list[0] < min
else min)
print(min_list(list))Thats also working, but only for lists with a length that is a power of two. For other lengths you just have to tweak the split into smaller arrays. The approach is taken from merge sort.
def findCloseToZero(l):
if len(l) == 1:
return l[0]
else:
first = findCloseToZero(l[0: int(len(l) / 2)])
sec = findCloseToZero(l[int(len(l) / 2): ])
return first
if abs(first) < abs(sec)
else secdef find_smallest_elem(lst):
k = 1
while k != len(lst):
if lst[0] > lst[k]:
return (find_smallest_elem(lst[k: ]))
else:
k += 1
return (lst[0])this is my answer using recursion and a line of code
def min_value(n_list):
return n_list[0]
if len(n_list) == 1
else min(n_list[0], min_value(n_list[1: ]))How to find the minimum number using anycodings_recursion recursion? The answer is 2.,This is a recursive implementation of anycodings_python min:,I am trying to import two files as lists or arrays and then compare that everything in list one is in list two ,Given this sample list:
Given this sample list:
[5, 3, 9, 10, 8, 2, 7]This is a recursive implementation of anycodings_python min:
l=[5, 3, 9, 10, 8, 2, 7]
def find_min(l,current_minimum = None):
if not l:
return current_minimum
candidate=l.pop()
if current_minimum==None or candidate<current_minimum: return find_min(l,candidate) return find_min(l,current_minimum) print find_min(l)>>>
2>>>
import random
>>>
arr = [random.randint(0, 8) for r in xrange(10)] >>>
arr[8, 2, 5, 1, 2, 4, 0, 3, 1, 1] >>>
def func(arr):
if len(arr) == 1:
return arr[0]
else:
return min(arr[0], func(arr[1: ]))
>>>
f(arr)
0This answer uses an accumulator to store anycodings_python the min value throughout the recursions.
list = [5, 3, 9, 10, 8, 2, 7]
def min_list(list, min = None):
if len(list) < 1:
return min
return min_list(list[1: ], list[0]
if min is None or list[0] < min
else min)
print(min_list(list))Thats also working, but only for lists anycodings_python with a length that is a power of two. anycodings_python For other lengths you just have to tweak anycodings_python the split into smaller arrays. The anycodings_python approach is taken from merge sort.
def findCloseToZero(l):
if len(l) == 1:
return l[0]
else:
first = findCloseToZero(l[0: int(len(l) / 2)])
sec = findCloseToZero(l[int(len(l) / 2): ])
return first
if abs(first) < abs(sec)
else secdef find_smallest_elem(lst):
k = 1
while k != len(lst):
if lst[0] > lst[k]:
return (find_smallest_elem(lst[k: ]))
else:
k += 1
return (lst[0])The recursive method can also be used for finding the minimum number in a list.,In Haskell, the maximum number in a list can be found using the recursive method.,The code below shows the minNum function being called by itself, through recursion. The first line is the declaration of the function indicating the data type of the parameters and the return value. Ord b specifies a type-class constraint, i.e., it can be of any data type that is orderable. The data type of parameter [b] is list, and the data type of the return value b is an integer.,If the list has more than one element, minNum calls itself recursively to first compare the initial two elements. Then, minNum compares the previous minimum number with the next entry of the list. It keeps on doing this until it reaches the end of the list, where it returns the minimum number.
maxNum::Ord a => [a] - > a
maxNum[x] = x
maxNum(x: x ':xs) = maxNum ((if x >= x'
then x
else x '):xs)
main = print(maxNum[2, 6, 3, 70, 1])minNum::Ord b => [b] - > b
minNum[x] = x
minNum(x: x ':xs) = minNum ((if x <= x'
then x
else x '):xs)
main = print(minNum[1, -2, 3, -24, 64])Problem Description: Given an array A[] of size n, you need to find the maximum and minimum element present in the array. Your algorithm should make the minimum number of comparisons.,We initialize both minimum and maximum element to the first element and then traverse the array, comparing each element and update minimum and maximum whenever necessary.,We have initialized maximum and minimum with the first element of the array - why?,In this approach, we pick array elements in pairs and update the min and max. If the array size is odd, we initialize the first element as both min and max, and if it's even, we compare the first two elements and initialize min and max accordingly.
Pseudo-Code
int[] getMinMax(int A[], int n) {
int max = A[0]
int min = A[0]
for (i = 1 to n - 1) {
if (A[i] > max)
max = A[i]
else if (A[i] < min)
min = A[i]
}
// By convention, let ans[0] = maximum and ans[1] = minimum
int ans[2] = {
max,
min
}
return ans
}Pseudo Code
int[] findMinMax(int A[], int start, int end) {
int max;
int min;
if (start == end) {
max = A[start]
min = A[start]
} else if (start + 1 == end) {
if (A[start] < A[end]) {
max = A[end]
min = A[start]
} else {
max = A[start]
min = A[end]
}
} else {
int mid = start + (end - start) / 2
int left[] = findMinMax(A, start, mid)
int right[] = findMinMax(A, mid + 1, end)
if (left[0] > right[0])
max = left[0]
else
max = right[0]
if (left[1] < right[1])
min = left[1]
else
min = right[1]
}
// By convention, we assume ans[0] as max and ans[1] as min
int ans[2] = {
max,
min
}
return ans
}For counting the number of comparisons, since this is a recursive function, let us define the recurrence relation :
T(n) = 2 T(n / 2) + 2
T(2) = 1
T(1) = 0
We can solve this recurrence relation by master method / recursion tree method.
if n is a power of 2
T(n) = 3n / 2 - 2We can use recursion to find the element with the minimum value in a list, as shown in the code below. ,Computing the value of a Fibonacci number can be implemented using recursion. Given an input of index N, the recursive function has two base cases – when the index is zero or 1. The recursive function returns the sum of the index minus 1 and the index minus 2. ,One can model recursion as a call stack with execution contexts using a while loop and a Python list. When the base case is reached, print out the call stack list in a LIFO (last in first out) manner until the call stack is empty.,A nested list can be traversed and flattened using a recursive function. The base case evaluates an element in the list. If it is not another list, the single element is appended to a flat list. The recursive step calls the recursive function with the nested list element as input.
def myfunction(n): if n == 0: return n
else: return myfunction(n - 1) myfunction(1000) #results in stack overflow errorFibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
5 / \/ \ 3 8 /\ / \2 4 7 9
def flatten(mylist): flatlist = []
for element in mylist: if type(element) == list: flatlist += flatten(element)
else: flatlist += element
return flatlist print(flatten(['a', ['b', ['c', ['d']], 'e'], 'f'])) # returns['a', 'b', 'c', 'd', 'e', 'f']def fibonacci(n): if n <= 1: return n
else: return fibonacci(n - 1) + fibonacci(n - 2)def countdown(value): call_stack = []
while value > 0: call_stack.append({
"input": value
}) print("Call Stack:", call_stack) value -= 1 print("Base Case Reached") while len(call_stack) != 0: print("Popping {} from call stack".format(call_stack.pop())) print("Call Stack:", call_stack) countdown(4)
''
'Call Stack: [{'
input ': 4}] Call Stack: [{'
input ': 4}, {'
input ': 3}] Call Stack: [{'
input ': 4}, {'
input ': 3}, {'
input ': 2}] Call Stack: [{'
input ': 4}, {'
input ': 3}, {'
input ': 2}, {'
input ': 1}] Base Case Reached Popping {'
input ': 1} from call stack Call Stack: [{'
input ': 4}, {'
input ': 3}, {'
input ': 2}] Popping {'
input ': 2} from call stack Call Stack: [{'
input ': 4}, {'
input ': 3}] Popping {'
input ': 3} from call stack Call Stack: [{'
input ': 4}] Popping {'
input ': 4} from call stack Call Stack: []'
''