= Binary array sum by recursion
{title2=$S(A,l,r)=\sum_{i=l}^{r-1}A_i$}
Keep an <array> $A$ unchanged, and sum entries in the half-open <integer interval> of <array indices> $[l,r)$. The <precondition> requires <integers> $0\leq l\leq r\leq\operatorname{length}(A)$ and exact, terminating <integer> <addition>. An empty range returns the <empty sum> zero; a one-entry range returns that entry. Every longer range splits at its middle <array index>:
``
S(A, l, r):
require integer indices with 0 <= l <= r <= length(A)
size = r - l
if size == 0:
return 0
if size == 1:
return A[l]
middle = l + floor(size / 2)
left_sum = S(A, l, middle)
right_sum = S(A, middle, r)
return left_sum + right_sum
``
For the original <array> $A=[6,-2,5,1]$, call $S(A,0,4)$. The left half returns $6+(-2)=4$, the right half returns $5+1=6$, and the original invocation returns $4+6=10$. The right half's left endpoint increases from zero to two: what decreases is range length $r-l$, not every argument. Negative entries affect the answer but do not affect <algorithm termination>.
\Image[/recursion-binary-array-sum-call-tree.png]
{title=Seven calls compute an array sum with only three frames active at once}
{description=Original <binary tree> of invocations for $A=[6,-2,5,1]$, with <integer intervals> labeling ranges and upward arrows labeling returned sums. Small numbers give the order in which invocations begin when the left child runs first. The highlighted <graph path> contains the three active <stack frames> while the entry $-2$ is read; the result $6$ from the completed left sibling is retained by its parent.}
For range length $n=r-l\geq2$, the children have lengths $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$, both positive and strictly less than $n$. The <floor function> chooses the split; the <ceiling function> gives the other length. <Algorithm termination> follows by this <natural number> measure. For <algorithm correctness>, apply <mathematical induction> on $n$: the two <base cases> return the specified <sum>; for a larger range, the two disjoint child ranges cover every original <array index> exactly once, so <addition> of their correct <sums> gives the required <sum>.
For $n\geq1$, the invocation <tree> is a <full binary tree> with $n$ leaves, one per <array> entry. If $I$ is its number of nonleaf <vertices>, counting <edges> gives $2I=I+n-1$, so $I=n-1$. Thus the total invocation count is $2n-1$, and there are $n-1$ combining <additions>. Here $n=4$ gives seven calls and three combining <additions>. For $n=1$, there is one call and no combining <addition>; for $n=0$, there is also one call and no combining <addition>, but no entry leaf, so the $2n-1$ formula does not apply.
The <call stack> holds the active branch, rather than the entire invocation <tree>. Execute the left child completely before the right child, retaining the left result in the parent <stack frame>. The maximum number of active <stack frames> is $1+\lceil\log_2 n\rceil$ for $n\geq1$, and one for $n=0$. Balanced splitting therefore needs $O(\log n)$ frames for $n\geq2$, compared with the $O(n)$ frames of the <factorial> <recursive process>. Assuming constant-cost <array> access, index operations and <addition>, its <time complexity> is $O(n)$ and its auxiliary <space complexity> is $O(\log n)$ <machine words> for $n\geq2$, excluding the stored <input>. Pass the same <array> with different endpoints, rather than copying slices. These bounds require all stored indices and partial sums to fit in a constant number of <machine words>; exact unbounded <integer> <addition> and storage require a separate <bit> cost analysis.
Back to article page
