Adding two strings made of digits recursively in C -

for problem, first take in 2 strings using fgets. need check if string comprised entirely of digits making number. able part recursively, next task if strings numbers, need sum them recursively well. example, output of program may this:

first number > 9023905350290349

second number > 90283056923840923840239480239480234

sum 90283056923840923849263385589770583

again, need recursively, thinking march along stream of digits , add them together, not sure how write program recursively. since input in character form, have convert integer, believe can converting individual characters integer ascii value subtracting 48 away it. appreciated. thanks!

you're on right track. recursive approach checking if input number looks following, right? notice can go ahead , subtract '0' character without bothering convert 48 yourself.

int number_length(char *s, int pos) {   int d;   if (s[pos] == '\0') {     return pos;   }   d = s[pos] - '0';   if (d < 0 || d > 9) {      return -1;   }    return number_length(s, pos+1); } 

the above function returns -1 if input invalid, , length of number otherwise. can use length of input numbers when start recursive addition process.

where should recursion begin? when add pair of numbers, convenient start least significant digits.

if have pair of char * variables a , b pointing numbers, , if know a contains a_length digits , b contains b_length digits, then:

• the least significant digit of a @ a_length-1.

• the least significant digit of b @ b_length-1.

we don't know in advance how long result going be, let's build digits in int * array starting position 0. means we'll have result digits in reverse, we'll print them out starting end , going 0.

the core of computation this:

• given position a_pos in a , b_pos in b, carry digit carry, compute sum of digits in a , b carry digit.

• update carry digit.

• add result digit result array , update length of array.

in c, can express computation follows:

    d = a[a_pos--] + b[b_pos--] - 2*'0' + carry;     carry = (d >= 10 ? 1 : 0);     result[result_pos++] = d%10; 

the expression a[a_pos--] + b[b_pos--] becomes invalid once a_pos or b_pos has become negative. in other words, must deal situations have run out of digits in 1 or both numbers. must take care to:

• handle cases we've processed significant digit of a not b, or b not a.

• when we've reached end of both a , b, remember check carry digit: if it's 1, add result , increment length of result.

below complete implementation in ansi c.

#include <stdio.h> #include <string.h>  #define buffer_size 8192  char a[buffer_size], b[buffer_size]; int result[buffer_size];  int number_length(char *s, int pos) {   int d;   if (s[pos] == '\0') {     return pos;   }   d = s[pos] - '0';   if (d < 0 || d > 9) {      return -1;   }    return number_length(s, pos+1); }  int add(char *a, int a_pos, char *b, int b_pos,     int *result, int result_pos, int carry) {   int d;   if (a_pos < 0 && b_pos < 0) {     if (carry == 1) {       result[result_pos++] = 1;     }     return result_pos;   }   if (a_pos < 0) {     result[result_pos++] = b[b_pos--] - '0' + carry;     carry = 0;   } else if (b_pos < 0) {     result[result_pos++] = a[a_pos--] - '0' + carry;     carry = 0;   } else {     d = a[a_pos--] + b[b_pos--] - 2*'0' + carry;     carry = (d >= 10 ? 1 : 0);     result[result_pos++] = d%10;   }   return add(a, a_pos, b, b_pos, result, result_pos, carry);  }  int main() {   int a_length, b_length, i, result_length;   printf("first number > ");   scanf("%s", a);    if ((a_length = number_length(a, 0)) == -1) {     printf("%s not number.\n", a);     return 0;   }   printf("second number > ");   scanf("%s", b);    if ((b_length = number_length(b, 0)) == -1) {     printf("%s not number.\n", b);     return 0;   }   result_length = add(a, a_length-1, b, b_length-1, result, 0, 0);   (i = result_length-1; >= 0; --i) {     printf("%d", result[i]);   }   printf("\n");   return 0; }