[SOLVED] Basic arithmetic operation using recursive function

Question

I'm trying to write a recursive function which applies a certain basic arithmetic operation on each digit of a given number passed as argument. So far I've only managed to do addition and multiplication, yet I'm not sure I'm doing it right, cause I'm stuck on trying to apply other operation.

Please help me make this code do what it was supposed to do SoloLearners 🙏

https://code.sololearn.com/c5izvgzl4D70/?ref=app

Answer 1

Ipang I agree, recursion can be tricky. For me, it helps to perform substitution on an example.
I'll ignore op and pretend this is addition for simplicity.

rec(123)
3 + rec(12)
3 + (2 + rec(1)) // rec(1) is the base case. stop now
3 + (2 + 1)

The parentheses are needed because of how function calls are evaluated first and that returning is not direct substitution (unlike macros). It may become clear with variables:

int a = 1;
int b = 2 + a; // 2 + (1)
int c = 3 + b; // 3 + (2 + a) not 3 + 2 + a

Unfortunately, I don't have a better explanation about base cases other than its definition: the stopping condition for a recursive function. Your function should stop when you reach the last digit, hence n < 10.

Answer 2

return n % 10 + rec(n / 10, op);
expand this and you get 5+(4+(3+(2+(1+0))))
If you try this for subtract/divide you'll easily see why it's wrong 5-(4-(3-(2-(1-0))))=3 but 1-2-3-4-5=-13 (subtraction and division are not commutative, a-b != b-a)

Flipping it around with your current base case isn't quite right though:
return rec(n / 10, op) - n % 10;
// expand: ((((0-1)-2)-3)-4)-5=-15

Your base case should be n < 10. Removing the switch case at the bottom and just returning n would give you (((1-2)-3)-4)-5=1-2-3-4-5=-13

if (n >= 10)
{
switch (op)
{
// other cases
case SUBTRACT:
return rec(n / 10, op) - n % 10;
// other cases
// same for division
}
}
return n;

Answer 3

Ipang
I don't really see any problem with your current code. Why aren't you doing it the same way you've doing addition and multiplication (although I would say, if you're taking `n` as int, division would mostly return 0)?

Answer 4

Shahzad
I tried it buddy, but I didn't succeed at subtraction (not getting expected result). So that's why I ask where I'm wrong, cause if I did it right, I should have gotten the expected result.

Thank you 🙏

Answer 5

jtrh
Let me try to digest your explanation, recursion isn't as easy for me to understand.

When I do this, it starts with last digit down to the first.
return n % 10 + rec( n / 10, op );

And when I do this, it starts at first digit up to the last.
return rec( n / 10, op ) + n % 10;

But I didn't have those parentheses around the numbers as per your expanded example. So I thought it will simply do 5 + 4 + 3 + 2 + 1

How do I train myself to be able to pictorially imagine the recursion expansion?

And about the removal of the switch block at the bottom, I added switches when I found that I had to return 1 when I'm multiplying (not adding). But your suggestion that the base case should be n < 10, kind of explained why it is unnecessary.

Any tips for analysing a recursion base case please?

And Thank you 🙏

Answer 6

jtrh
I think I'm starting to understand a bit better (I hope). The parentheses are there to emphasise the recursive function work, to clear up on what is happening where.

And to conclude this case, I had two issues in the code, that is

1. Wrong base case.
2. Wrong starting point. I should start working from the first digit up to the last.

Thank you once again, 🙏

Answer 7

XXX
You're right, integer division doesn't make sense cause result might mostly be zero. I think I'll remove the option once I clearly understand my fault in this code.

Thank you 🙏