sum function with divide and conquer algorithm

Overview

By divide and conquer algorithm, I’ll write sum function. This article is my personal memo about a book.

Motivation

These days, I have been reading Functional Programming in Scala. In the book, there is an example of divide and conquer algorithm. So, as a reading memo, I’ll leave the simple note and code with Python.

What is divide and conquer algorithm?

The concept of divide and conquer algorithm is simple. It has three steps, Divide, Conquer and Combine. The given problem is divided into subproblems and recursively solved. In the end, the answers are combined.

Writing SUM function with divide and conquer algorithm

The code for sum with divide and conquer algorithm is simple. With less than ten lines, we can write.

def original_sum(some_list):
    if len(some_list) == 1:
        return some_list[0]
    split_point = len(some_list) // 2
    l_list = some_list[:split_point]
    r_list = some_list[split_point:]
    return original_sum(l_list) + original_sum(r_list)
      

With the list, [1,2,3,4,5], we can check if it works.

original_sum([1,2,3,4,5])

15

It's working.

But this kind of recursive function is bit confusing until you are used to. So, Let's trace how it is working.

I can express this case with the image below.



The list is divided into two if the length of that is bigger than one. When the list is enough split until the length is one, the recursive stops and the value of the list is extracted. As a consequence, the bottom nodes of the image are summed up.
On the book, Functional Programming in Scala, this came with the context of multi processing. The problem is divided into parts and each core can calculate their own part.