How to change a for loop to a recursive function?

Hi!

I'm new to Matlab but I'm trying my best to improve as quickly as possible. I'm trying to make a function just by using recursion, which is really new to me. I've got this

res=[0,res]
for N=(length(res):-1:2)
    if res(N)>9
        res(N)=res(N)-10;
        res(N-1)=res(N-1)+1;
    end
end

which in theory will make array 'res' into single digit cells. The value of each original cell never surpasses 18.

This is not for any school project or anything marked. This is an enquiry to improve my matlab skills.

Can you help me? What is the best way to transform this into a recursive function?

Thank you in advance,

EKB

Answer 1

[Guillaume]

I'm not sure why you would want to replace your loop by a recursive function as it's often less efficient. It's certainly possible, you would call you recursive function with an array shorter by one element, with a carry at each step. Something like:

function res = singledigit(res)
   res = recurse([0 res], 0);
end

function res = recurse(res, carry)
   res(end) = res(end) + carry;
   carry = floor(res/10);
   res(end) = mod(res(end), 10);
   if numel(res) > 1
      res(1:end-1) = recurse(res(1:end-1), carry);
   end
end

I don't see that as any better as your loop. What would be better however would be to vectorise the calculation. As you know that no value is never greater than 18, the carry will never be more than 1 and adding the carry before doing a modulus will never bring any value above 19. Thus the following is guaranteed to work:

res = mod([0 res] + [floor(res/10) 0], 10);

[Emma]

Thank you Guillaume. I agree with you that recursion probably isn't the best method. Many thanks for your complete answer. The last piece of coding has helped me a lot. (Eye-opener for me). Many thanks again.

[Guillaume]

Actually, I made a mistake. I thought the carry could not cascade more than once to the left, but that is wrong when any value is 9. My one-liner will not work for example for:

res = [1 9 10]; %fail to propagate carry properly

A while loop would solve it:

res = [0 res];
carry = [floor(res(2:end)/10) 0];
while any(carry)
   res = mod(res, 10) + carry;
   carry = [floor(res(2:end)/10) 0];
end

Note that this latter function does not even need the restriction that any number is smaller than 18.