Nested Sum

Assignment

In Doc2Doc, users can process files or entire directories. We need to know the total size of those files and directories (measured in bytes).

Due to the nested nature of directories, we represent a root directory as a list of lists. Each list represents a directory, and each number represents the size of a file in that directory. For example, here's a directory that contains 2 files at the root level, then a nested directory with its own two files:

root = [
    1,
    2,
    [3, 4]
]
print(sum_nested_list(root))
# 10

Here's a more complex example:

root
├── scripts.txt (5 bytes)
├── characters (dir)
│   ├── zuko.txt (6 bytes)
│   └── aang.txt (7 bytes)
└── seasons (dir)
    ├── season1 (dir)
    │   ├── the_avatar_returns.docx (8 bytes)
    │   └── the_southern_air_temple.docx (9 bytes)
    └── season2_notes.txt (10 bytes)

Which would be represented as:

root = [
    5,
    [6, 7],
    [[8, 9], 10]
]
print(sum_nested_list(root))
# 45

Complete the sum_nested_list function. It takes a nested list of integers as input and should return the total size of all files in the list. It's a recursive function.

Here's some pseudocode to help you get started:

1. Create an integer variable to keep track of the total size.

2. For each item in the list (use a loop here):

   1. If the item is an integer, add it to the total size.

   2. If the item is a list, use a recursive call to sum_nested_list to get the size of that list. Add that size to the total size.

3. Return the total size when you're done iterating.

You can use loops with recursion. While functional programming avoids loops, recursion can be used outside functional programming.

You can use the built-in isinstance function to check if an item is an integer or a list:

isinstance(5, list)
# False
isinstance([5, 6], list)
# True

Solution

def sum_nested_list(lst):
    total = 0
    for element in lst:
        if isinstance(element, list):
            total += sum_nested_list(element)
        else:
            total += element
    return total

Let's break it down in simple terms:

1. Function Purpose: This function, called sum_nested_list, adds up all the numbers in a list, even if some of those numbers are inside other lists (nested lists).

2. Step-by-Step:

   • Start with Zero: It begins by setting a variable totalSize to 0. This variable will hold the running total of all the numbers.

   • Loop Through Each Item: It then goes through each item (x) in the list:

     • If the Item is a Number: If x is an integer (a number), it adds that number to totalSize.

     • If the Item is a List: If x is another list, the function calls itself with that list (this is the recursive part). It gets the total of that inner list and adds that result to totalSize.

   • Return the Total: After checking every item, the function returns the final total (the sum of all the numbers).

3. Why Use Recursion? Recursion means the function calls itself. This is useful here because the list might contain more lists inside it. The function will keep calling itself until it reaches lists that only contain numbers, and then it adds them up.

In summary, the function goes through each part of a possibly nested list structure, sums up all the numbers it finds, and then returns that sum.