6
$\begingroup$

I was reading page 147 of Goodrich and Tamassia, Data Structures and Algorithms in Java, 3rd Ed. (Google books). It gives example of linear sum algorithm which uses linear recursion to calculate sum of all elements of the array:

Algorithm linearSum (arr , n)
    if (n == 1)
        return arr[0] 
    else
        return linearSum (arr , n-1) + arr[n-1]
end linearSum

And the binary sum algorithm which uses binary recursion to calculate sum of all elements of the array:

Algorithm binarySum (arr, i, n)
    if (n == 1)
        return arr[i]
    return binarySum (arr, i, ⌈n/2⌉) + binarySum (arr, i+⌈n/2⌉, ⌊n/2⌋)
end binarySum

It further says:

The value of parameter $n$ is halved at each recursive call binarySum(). Thus, the depth of the recursion, that is, the maximum number of method instances that are active at the same time, is $1 + \log_2 n$. Thus the algorithm binarySum() uses $O(\log n)$ additional space. This is big improvement over $O(n)$ needed by the linearSum() algorithm.

I did not understood how the maximum number of method instances that are active at the same time, is $1 + \log_2n$.

For example consider the below calls to method with method parameters given in rounded box:

enter image description here

Then in two recursive calls of second row from top, $n = 8$. So, $1 + \log_2 8 = 4$. Now I dont get what maximum limit this 4 represent?

$\endgroup$
  • 3
    $\begingroup$ Height of this tree is 4. All the vertices of this tree correspond to binarySum calls. Each a binarySum call finishes after all its children finish. So, when binarySum on the leaves level is active, its parent, grandparent and so on are still active as well. It's called a depth of recursion, which is equal to the height of this tree. $\endgroup$ – HEKTO Aug 14 '14 at 22:06
  • 1
    $\begingroup$ HEKTO is right. Perhaps when you learn about call stack and method context frames in call stack, you will see this even clearer. $\endgroup$ – InformedA Aug 15 '14 at 4:45
  • 1
    $\begingroup$ Ohh great. @hekto please put it in answer $\endgroup$ – anir123 Aug 15 '14 at 6:30
6
$\begingroup$
  • In a given tree, all the vertices of this tree correspond to binarySum() calls.
  • The value of parameter n to binarySum() is halved at each recursive call.
  • Also, each recursive call finishes after all its children finish. Thus at each recursive call, number of active calls include all the ancestor calls in call sequence.
  • Thus when any binarySum() call corresponding to leaves in above call tree is active, its parent, grandparent and so on are still active as well.
  • Thus, the depth of the recursion, that is, the maximum number of method instances that are active at the same time, which is always equal to the height of the recursive calls tree is 1 + log$_2$n.
  • For example in binarySum() recursive calls tree above, with n = 8, at any of the calls correspnding to leaves,

enter image description here

Why does the depth of recursion affect the space, required by an algorithm? Each recursive function call usually needs to allocate some additional memory (for temporary data) to process its arguments. At least, each such a call has to store some information about its parent call - just to know where to return after finishing. Let's imagine you are performing a task, and you need to perform a sub-task inside this first task - so you need to remember (or write down on a paper) where you stopped in the first task to be able to continue it after you finish the sub-task. And so on, sub-sub-task inside a sub-task... So, a recursive algorithm will require space O(depth of recursion).

@randomA mentioned the Call Stack, which is normally used when a function invokes another function (including itself). The call stack is the part of the computer memory, where a recursive algorithm allocates its temporary data.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.