A nested list is given. The task is to print the sum of this list using recursion. A nested list is a list whose elements can also be a list.
Examples :
Input: [1,2,[3]] Output: 6 Input: [[4,5],[7,8,[20]],100] Output: 144 Input: [[1,2,3],[4,[5,6]],7] Output: 28
Recursion: In recursion, a function calls itself repeatedly. This technique is generally used when a problem can be divided into smaller subproblems of the same form.
Implementation:
Iterate through the list and whenever we find that an element of the list is also a list that means we have to do the same task of finding the sum with this element list (which can be nested) as well. So we have found a subproblem and, we can call the same function to perform this task and just change the argument to this sublist. And when the element is not a list, then simply add its value to the global total variable.
Python3
# Python Program to find sum# of nested list using Recursiondef sum_nestedlist( l ): # specify that global variable is # referred to here in this function total = 0 for j in range(len(l)): if type(l[j]) == list : # call the same function if # the element is a list total+= sum_nestedlist(l[j]) else: # if it's a single element # and not a list, add it to total total += l[j] return total print(sum_nestedlist([[1,2,3],[4,[5,6]],7])) |
28
Time Complexity: O(N), Where N is the total number of elements in the list.
Auxiliary Space: O(1)
Method 2: Using recursion
This program defines a function sum_nestedlist that takes a nested list as input and returns the sum of all its elements. It does this by using a stack to iterate through each element of the list, adding each non-list element to a running total and extending the stack with any list elements.
Python3
def sum_nestedlist(l): stack = l total = 0 while stack: elem = stack.pop() if type(elem) == list: stack.extend(elem) else: total += elem return total# example usagemy_list = [[1,2,3],[4,[5,6]],7]print(sum_nestedlist(my_list)) # Output: 28 |
28
Time complexity: O(n), where n is the total number of elements in the nested list.
Auxiliary space: O(d), where d is the maximum depth of nesting in the input list.
Method 3: Using Iteration
This function uses a stack to keep track of nested lists. It pops the last element from the stack, and if it’s a list, it pushes its elements to the stack. If it’s a number, it adds it to the total.
Follow the below steps to implement the above idea:
- Define a function sum_nestedlist_iterative(lst) that takes a nested list lst as input.
- Initialize a variable total to 0 and a list stack containing the input last.
- Enter a while loop that continues until the stack list is empty.
- Pop the last element from the stack list and assign it to current.
- For each element in current, check if it is a list. If it is a list, append it to the stack list. If it is not a list, add the element to the total variable.
- Repeat steps 4-5 until all elements in lst have been checked.
- Return the final value of total.
Below is the implementation of the above approach:
Python3
def sum_nestedlist_iterative(lst): total = 0 stack = [lst] while stack: current = stack.pop() for element in current: if type(element) == list: stack.append(element) else: total += element return totalprint(sum_nestedlist_iterative([[1,2,3],[4,[5,6]],7])) |
28
Time complexity: O(n), where n is the total number of elements in the nested list.
Auxiliary space: O(m), where m is the maximum depth of the nested list.
Method 4: Using a Stack
Step-by-step approach:
- Initialize an empty stack and push the input list onto it.
- Initialize the sum variable to 0.
- While the stack is not empty:
a. Pop the top element from the stack.
b. If the element is a list, push all its elements onto the stack.
c. If the element is an integer, add it to the sum variable. - Return the sum variable.
Python3
def sum_nestedlist(l): stack = [] stack.append(l) total = 0 while stack: curr = stack.pop() if type(curr) == list: for elem in curr: stack.append(elem) else: total += curr return totalprint(sum_nestedlist([[1,2,3],[4,[5,6]],7])) |
28
Time Complexity: O(N), where N is the total number of elements in the input list.
Auxiliary Space: O(M), where M is the maximum size of the stack during the execution of the program.
Method 5: Using Queue
step-by-step approach:
- Define a function named sum_nestedlist_queue that takes in a nested list lst as input.
- Initialize a variable named total to 0 to keep track of the sum of all the elements in the nested list.
- Create a queue using the deque function from the collections module. The queue should be initialized with the input nested list lst.
- Start a loop that continues as long as the queue is not empty. The loop will pop the first element in the queue (using the popleft method), and assign it to a variable named current.
- For each element in current, check if it is a list by using the type function. If the element is a list, append it to the end of the queue using the append method.
- If the element is not a list, add it to the total variable.
- Repeat steps 4-6 until the queue is empty.
- Return the final value of total.
- Call the sum_nestedlist_queue function with an example nested list, and print the result.
Python3
from collections import dequedef sum_nestedlist_queue(lst): total = 0 queue = deque([lst]) while queue: current = queue.popleft() for element in current: if type(element) == list: queue.append(element) else: total += element return totalprint(sum_nestedlist_queue([[1,2,3],[4,[5,6]],7])) |
28
Time complexity: O(n), where n is the total number of elements in the nested list.
Auxiliary space: O(max_depth), where max_depth is the maximum depth of the nested list.
