1

How should I write a tail recursive function to compute the sum of a vector? The function takes 2 input arguments: a vector v and sum. Tail recursion means that the last part of the function must call itself.

I have a basic shell of what the function should look like, but I am unsure about how to write the recursive part.

function result = vectorSum(v,sum)
%takes a vector v and the returns the sum of all elements in the vector
if length(v) == 0
    result = 0;
elseif length(v) == 1
    result = v;
else
    result = vectorSum(v,sum)
end
end

The function returns a result of 0 for an empty vector, and if the vector's length is 1 it returns the value v(1).

ibezito
  • 5,782
  • 2
  • 22
  • 46
Vladamir
  • 247
  • 1
  • 3
  • 11
  • 4
    If `length(v)>1` then your code does nothing, and passes the same inputs into itself again. That can't be correct! – David May 23 '16 at 01:10
  • 3
    Where do you perform a `sum`? Where do you reduce the size `v` in the recursion such that the execution ultimately terminates? In addition to those comments, I will say that Matlab, as far as I know, doesn't do tail recursion optimization and deeply recursive code tends to perform more poorly than iterative. – TroyHaskin May 23 '16 at 01:17

1 Answers1

2

Your solution has two main problems:

  1. The results are not accumulated - You simply call the vectorSum function without considering the result from previous calls.
  2. The size of the problem is not reduced at each recursive call.

The are several ways to implement this recursion, I suggest the following approach:

function result = vectorSum(v)
%takes a vector v and the returns the sum of all elements in the vector
if length(v) == 0
    result = 0;
else
    result = v(end) + vectorSum(v(1:end-1));
end
end
ibezito
  • 5,782
  • 2
  • 22
  • 46