CODEWITHSUNDEEP
calgorithmrecursion
good question
good question

Reputation: 17

Recursive function to add sum of sequence of numbers and the sums thereof

This was an interview question:

Given a sequence of n numbers (n can be any number, assume n <= 100 for this question), say for eg. 11, 23, 9, 17, 20, 8, 5, 6 . Problem is to write a recursive function in C to add each number in the sequence to get the sum. If this sum is of more than one digit then sum the digits again and again if the sum is of more than one digit then sum the digits again. Follow this process until the sum is reduced to one digit no. Now add all the sums obtained in the process to output the final sum.

For illustration take above sequence: 11, 23, 9, 17, 20, 8, 5, 6

SUM(11, 23, 9, 17, 20, 8, 5, 6) = 99 => SUM(9, 9) = 18 => SUM(1, 8) = 9

Now add all the sums obtained, i.e. SUM(99, 18, 9) = 126 <== should be the output.

Please note that the function should be a recursive function in C.

Upvotes: 0

Views: 6260

Answers (7)

Pavi
Pavi

Reputation: 61

#include <iostream>
using namespace std;

class RecursiveSum {
public:
    int nDigits(int a) {
        int d = 0;
        while (a > 0) {
            d++;
            a /= 10;
        }
        return d;
    }

    long sum(int *arr, int b, int e, int s) {
        if (!arr)
            return 0;
        if (b < e) {
            s += arr[b++];
            return sum(arr, b, e, s);
        } else { // b >= e
            if (s < 10)
                return s;

            int nd = nDigits(s);
            int* narr = new int[nd];
            long n = s, itr = 0;
            while (n > 0) {
                narr[itr++] = n % 10;
                n /= 10;
            }

            s += sum(narr, 0, nd, 0);
            delete[] narr;

            return s;
        }
    }

};

Upvotes: 0

Bangonkali
Bangonkali

Reputation: 1150

I just want to add this one to 77v's answer in order to make everything hardcore recursive as possible. I know this is a year ago already, and his C++ solution works quite nice already. But I really had no fun that I though I can make that one last function called sumDigits in to recursion. So to rid myself of boredom, here it is:

long sumDigits(long x, long d = 0)
{
    if (x != 0)
    {
        d = x % 10;
        return d + sumDigits(x / 10, d);
    }
    else
        return 0;
}

It's the same, 7 lines long and accepts one argument. Note that the second one is defaulted to 0. It's used as a memory for the recursion itself. The user may ignore that second argument entirely. The function is also used the same way as 77v's implementation. You can in fact directly replace his function with this one. Hence making all the function in his solution recursion based. Which makes an already awesome work more awesome! Lol! :D

Upvotes: 0

pierrotlefou
pierrotlefou

Reputation: 40721

As others had said : the point here is to understand the recursion.

There are 3 place we can use recursion :

  • sum all the digits in a Integral number: 

    sum_digital :: (Integral a) => a -> a
sum_digital d
   | d < 10     = d
   | otherwise  = d `mod` 10 + sum_digital (d `div` 10)

  • chain all the sums from a start value and the rules

    chain :: (Integral a) => a -> [a]
chain a 
    | a < 10 = [a]
    | otherwise = a : chain (sum_digital a)

  • final one. sum of a list 

    mySum :: (Integral a) => [a]-> a
mySum [] = 0
mySum (x:xs) = x + mySum xs

Put all these together: 

*Main> mySum $ chain $ mySum [11, 23, 9, 17, 20, 8, 5, 6]    
126

The C version is left for you as the exercise:)

Upvotes: 0

Ula Krukar
Ula Krukar

Reputation: 12999

Here's a Scala implementation:

def sum(lst: List[Int]): Int = {
    val sum1 = lst.reduceLeft(_+_)
    println(sum1)
    sum1 match {
       case nb if nb < 10 => sum1
       case _ => {
            val lst2 = sum1.toString.toList.map(_.toString).map(Integer.parseInt(_))
            sum1 + sum(lst2)
       }
    }

}

val lst = List(11, 23, 9, 17, 20, 8, 5, 6)
val totalSum = sum(lst)
println(totalSum)

Result:

99
18
9
126

I'm really beginning to love, how concise Scala is.

Upvotes: 0

77v
77v

Reputation: 

#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>

const int n = 8;

int sumDigits(int x)
{
    int d = 0;

    while (x != 0)
    {
        d += x % 10;
        x /= 10;
    }

    return d;
}

int sumArr(int* a, int start)
{
    return (start == n)? 0: a[start] + sumArr(a, start + 1);
}

int sum(int x)
{
    return (x < 10)? x: x + sum(sumDigits(x));
}

int main(int argc, _TCHAR* argv[])
{
    int* a = new int[n];
    a[0] = 11; a[1] = 23; a[2] = 9; a[3] = 17; a[4] = 20; a[5] = 8; a[6] = 5; a[7] = 6;
    //for (int i = 0; i < n; i++) a[i] = rand() % 100;
    //for (int i = 0; i < n; i++) printf("a[%d] = %d\n", i, a[i]);

    printf("sum = %d\n", sum(sumArr(a, 0)));

    return 0;
}

This outputs: sum = 126

Upvotes: 0

Steve Gilham
Steve Gilham

Reputation: 11277

Here's an Erlang implementation you could use as a guide

-module('summation').  
-export([start/1]).  

sumlist(List)->
  lists:foldl(fun(X, Sum) -> X + Sum end, 0, List). << Inherently recursive

num_to_list(Value) ->
  Str = integer_to_list(Value),
  lists:map(fun(X) -> X - 48 end, Str).  << Inherently recursive

accumulate([_H], List) ->
  io:fwrite("~w~n", [List]),
  List;
accumulate(Value, List) ->
  Tmp = sumlist(Value),
  accumulate(num_to_list(Tmp), [Tmp|List]).  % << Recurse here

start(List)->
  Value = accumulate(List, []),
  sumlist(Value).

testing

25> c(summation).
{ok,summation}
26> summation:start([11, 23, 9, 17, 20, 8, 5, 6]).
[9,18,99]
126
27>

Upvotes: 0

Jimmeh
Jimmeh

Reputation: 2862

Not sure about C, but the algorithm would look similar to this.

SUM(1, 2, ... n) = 1 + SUM(2, ... n) and so on to get the total, then repeat once the final number is found to be more than one digit.

Upvotes: 1

Related Questions