CODEWITHSUNDEEP
crecursion
cheroky
cheroky

Reputation: 757

Multiply digits of a number using recursion

I am doing the following exercise:

Given a four digit number such as 3183, compare each digit with the last and if greater or equal multiply it with the following

Example: for the number 3183 it would be n = 3*8*3 = 72.

My code:

#include <stdio.h>

int f ( int n )
{
    if ( n < 10 ) 
      return n ;
    return (((n/10) % 10) >= (n%10) ? ((n/10)10) : 1) * f((n/100 )* 10 + n % 10 ) ;
}

int main() 
{
    printf( "%d", f( 3183 );

    return(0);
}

Is there any way to shorten it or make it better?

Upvotes: 3

Views: 3964

Answers (4)

Kevin
Kevin

Reputation: 1151

Leave another approach more compacted than the original:

#include <stdio.h>

int f (int n, int u)
{
    if (u > n) return(1);
    return (n % 10 >= u ? n % 10 : 1) * f(n/10, u);
}

int main (void)
{
    int n = 3284;
    printf ("%d", f (n , n%10));

    return(0);
}

Upvotes: 3

unwind
unwind

Reputation: 399843

EDIT I mis-read this yesterday. No point in effectively re-creating @Red Alert's answer now, but I can't delete it either since't it's accepted so here goes.

I assume we can create our own "inner" function to maintain state. I also assume digits are to be processed from the right, the original example isn't clear.

static int g(int n, int ack, int last)
{
  const int here = n % 10;
  const bool mult = here >= last;

  if(n < 10)
    return mult ? here * ack : here;
  return g(n / 10, mult ? here * ack : ack, here);
}

int f(int n)
{
  return g(n, 1, 0);
}

Upvotes: 1

Red Alert
Red Alert

Reputation: 3816

Are you allowed to use an intermediate recursive function? This eliminates the extra math you are doing to maintain the state of the last digit:

int f2 ( int n, int lastDigit )
{
    int currentDigit = n%10;
    int returnDigit = currentDigit;
    if(currentDigit < lastDigit)
        returnDigit = 1;
    if(n < 10)
        return returnDigit;

    return returnDigit * f2(n/10, lastDigit );
}

int f ( int n )
{
    if ( n < 10 ) 
      return n ;
    return n%10* f2(n/10, n%10);
}

Upvotes: 0

chux
chux

Reputation: 153498

After accept answer

OP's code fails to compile, missing %

//     (((n/10) % 10) >= (n%10) ? ((n/10) 10) : 1) * f((n/100 )* 10 + n % 10 ) ;
return (((n/10) % 10) >= (n%10) ? ((n/10)%10) : 1) * f((n/100 )* 10 + n % 10 ) ;

As @interjay recommend, save results rather than recalculating.

#include <stdio.h>

int f(int n) {
  if (n < 10)
    return n;
  int lastdigit = n % 10;
  int nextlastdigit = (n / 10) % 10;
  return (nextlastdigit >= lastdigit ? nextlastdigit : 1)
      * f((n / 100) * 10 + lastdigit);
}

int main(void)   {
    printf( "%u", f(2183); // --> 24
    return(0);
}

To make better, I would reduce division calls and multiplication by 1. But better is subjective at this point.

unsigned cheroky(unsigned x) {
  if (x < 10)
    return x;
  unsigned lastdigit = x % 10;
  unsigned firstdigits = x / 10;
  unsigned lastfirstdigit = firstdigits % 10;
  unsigned nextx = firstdigits - lastfirstdigit + lastdigit;
  unsigned product = cheroky(nextx);
  if (lastfirstdigit >= lastdigit)
    product *= lastfirstdigit;
  return product;
}

To really improve, would use a non-recursive loop.

unsigned cheroky2(unsigned x) {
  unsigned lastdigit = x % 10;
  unsigned product = lastdigit;
  while (x >= 10) {
    x /= 10;
    unsigned nextdigit = x % 10;
    if (nextdigit >= lastdigit)
      product *= nextdigit;
  }
  return product;
}

Upvotes: 0

Related Questions