CODEWITHSUNDEEP
calgorithmrecursion
Constellation
Constellation

Reputation: 65

Recursive function to calculate successor of a numeric string

I want to write a recursive function which calculates Succ(‘2468’) = '2469'. ‘2468’ is a numeric string.

The exercice give me some predefined function such as last(ch), which returns the last caracter of a string, start(ch), returns ch without the last caracter, addEnd(ch, c), adds c at the end of ch and ask me to return a string as final result (i.e., suc("123")="124")

I tried this code but it works only for a string with 2 characters. If the length of my string is > 2, it doesn't work: 

int successor (char*ch)
{
 if (strlen (ch)==1)
 return (int(*ch))+1);
 else 
  return ((int(*ch))*10+successor(ch+1));}

Upvotes: 1

Views: 344

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23955

There seems to be no need for multiplication or use of powers. Given the extra predefined functions you indicated were provided, I think the intention here was for a recursive way to express long addition with carry. I don't know C but here's an illustration in JavaScript that has very close syntax. I hope this helps.

function successor(s){
  if (s.length == 1){
    if (s == '9'){
      return '10';
      
    } else {
      // Return the successor character,
      // not sure how this looks in C.
      return String.fromCharCode(
        s.charCodeAt(0) + 1);
    }
  }
  
  let rightmost = successor(last(s));
  
  // No carry so just return
  // the string with the last
  // character incremented
  if (rightmost != '10'){
    return addEnd(start(s), rightmost);
    
  // We have a carry so
  // continue the recursion
  } else {
    return addEnd(successor(start(s)), '0');
  }
}

function last(s){
  return s.substr(-1);
}
function start(s){
  return s.substr(0, s.length - 1);
}
function addEnd(s, c){
  return s + c;
}
    
console.log(successor('2999'));

Upvotes: 2

cdlane
cdlane

Reputation: 41872

A key problem is this logic:

(int(*ch))*10+successor(ch+1)

the multiplication by 10 is insufficient for larger numbers. We need to multiply by a power of 10 and we already calculated that power but didn't hang onto it:

strlen (ch)

or more specifically:

strlen(ch) - 1

A complete solution:

#include <math.h>
#include <stdio.h>
#include <string.h>

#define digit(c) (c - '0')

int successor(char *string)
{
    size_t power = strlen(string) - 1;

    if (power == 0)
    {
        return digit(*string) + 1;
    }

    return digit(*string) * pow(10, power) + successor(string + 1);
}

int main() {
    printf("%d\n", successor("2999"));

    return 0;
}

OUTPUT

> ./a.out
3000
>

TODO

What happens if successor() is passed an empty string:

printf("%d\n", successor(""));

How can you modify the code to fix this? First decide what the function should return in this situation. What happens if successor() is passed a string that represents a number too large to be contained in an int:

printf("%d\n", successor("8589934592"));

How can you modify the code to fix this? Again, first decide what the function should return in this situation.

Upvotes: 2

Related Questions