CODEWITHSUNDEEP
c#recursion
Roka545
Roka545

Reputation: 3626

Recursively add digits

I'm going through a problem on LeetCode and need a refresher on recursion. This is the question: 

Given a non-negative integer num, repeatedly add all its digits until 
the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, 
return it.

I've seen answers using while loops but I would like to try this with recursion. This is what I have so far:

public int AddDigits(int num) {
    if(num > 9)
    {
        num = (num%10) + (num/10);
        AddDigits(num);
    }
    else{
        return num;
    }
}

First, I get "Not all code paths return a value." but based on the if boolean check, shouldn't this be okay? Even if I add a return num after the else block, I still get 11. Using an input of 29, my solution returns 11, even though numeventually becomes 2. With my recursive solution above, the return num portion occurs several times (I tested with Console.WriteLine statements) - is this due to the stack?

Here's what I would like to know - why does code occur after a recursive call - or should recursive calls typically NOT include code after the recursive call?

Also, how can I get this to work with recursion and without the use of while loops?

Upvotes: 2

Views: 1388

Answers (4)

spender
spender

Reputation: 120450

So really two different operations, both of which can be stated recursively.

Operation 1 is to add all the digits of a number together:

int AddAllDigits(int n)
{
    return n < 10 ? n : (n % 10 + AddAllDigits(n / 10));
}

Operation 2 is to keep performing operation 1 until we only have a single digit:

int ReduceToSingleDigit(int n)
{
    return n < 10 ? n : ReduceToSingleDigit(AddAllDigits(n));
}

So now we can

ReduceToSingleDigit(123456789); //gives 9

Now, if we have available the goodness of C#6, we can make our recursive functions look a bit more stylish (or confusing, depending on your position) by reducing them to expression bodies instead of statement bodies.

int ReduceToSingleDigit(int n) => n < 10 ? n : ReduceToSingleDigit(AddDigits(n));

int AddDigits(int n) => n < 10 ? n : (n % 10 + AddDigits(n / 10));

Lovely.

Upvotes: 1

M.kazem Akhgary
M.kazem Akhgary

Reputation: 19149

You need to return value in both path's (if and else).

it could be this (changing AddDigits(num); to return AddDigits(num); also works (given in other answer), btw I don't know why, but It works)

public int AddDigits(int num, bool root = true) {
    if(num > 9)
    {
        var sum = num;

        if(root)
        {
            while(sum > 9)
            {
                sum = AddDigits(sum/10, false) + sum%10;
            }
            return sum;
        }
        else return AddDigits(num/10, false) + num%10;
    }
    else{
        return num;
    }
}

Call function like this

var result = AddDigits(123456789); // ;)

This is how the algorithm works.

       AddDigits(123456789)   (root of call)         45   (45 is bigger than 9.    AddDigits(45)     9 is not bigger than 9. return result.
                    ||                               /\   repeat. while(sum > 9))       ||           /\
                    \/                               ||                                 \/           ||
   9 + AddDigits(12345678)                           ||                            4 + AddDigits(5)= 9     
                    ||                               ||
                    \/                      9+8+7+6+5+4+3+2+1 = 45
9 + 8 + AddDigits(1234567)                           ||
                    ||                               ||
                   ....                              ||        
                    ||                               ||
                    \/                               ||
            9+8+7+6+5+4+3+2+1 (now going back and summing them all)

Upvotes: 3

hawkeyegold
hawkeyegold

Reputation: 129

Here's an example using Linq:

using System.Linq;

static int Singularize(int val)
{
  string str=val.ToString();
  int rslt=Enumerable.Range(0,str.Length).Select(i => str.Substring(i,1)).Select(int.Parse).Sum();
  return (rslt.ToString().Length==1) ? rslt : Singularize(rslt);
}

Returning the recursion call itself (when necessary) allows the CLR to leave the current call and move to the recursive call and reuse the same stack item. If you retain the current call (by making the recursive call return it's result to the current call) each call in the recursive chain will lump another straw on the camel's (stacks) back, until the camel breaks - i.e., a stack overflow error.

Upvotes: 1

OregonTrail
OregonTrail

Reputation: 9039

Here's a hint, won't produce the correct value but it will get you there.

(Another hint, your function needs to take two arguments)

public int AddDigits(int num) {
    if(num > 9)
    {
        num = (num%10) + (num/10);
        return AddDigits(num);
    }
    else{
        return num;
    }
}

Edit: Solution in Python

def ra(n):
  if n > 0:
    return n % 10 + ra(n / 10)
  else:
    return 0

Upvotes: 2

Related Questions