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

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.

Answer 1

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.

Answer 2

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>

Answer 3

#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

Answer 4

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.

Answer 5

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:)