Other count digits recursive

F

freejlr

My teacher sent me the following exercise in class, but the teacher didn't even bother to explain how he wanted us to build the code.

The code has to be in java, but it is the same if you can help me with an example in C I can understand it.

I have the following code:

Java: 
public static int countDigitsRecursive(long num) {
 
     
  int count = 0;
 
    if (num != 0) {
     
        return 1 + countDigitsRecursive(num / 10);
    }
 

    return count;
         
 }

Well the code is quite easy, I take a long, and I divide it between 10, until it is 0, and I add 1 to it.

But the problem is that if the digit I passed is 0, the function returns 0, but there is the problem since 0 is a digit, it would have to return 1.

But our teacher does not say anything about 0, but if I say that count is equal to 1, then when I pass a 0, it returns 1, which would be correct, but if I put another number it would return a count of more example if I put 123 me returns 4.

How could this problem be solved? Recursively if possible. I don't know how to take the problem.

Thanks.
 
Your analysis of the function is incorrect. Zero is the termination condition of that recursive function. Passing 0 will always return 0 and has to, otherwise you'd always recurse forever.

Integer division of 1 into 10 yields 0, so the function will recurse once and return 1+0 which is one. This is also true for the the digits 2-9.

Integer division of 10 into 10 yields 1, so the function with recurse twice and give you 1+1+0 =2. Same for digits 11-19.
 
Is the java program ok ? If not fix first the java program.
Is the result ok for the unit tests as input 0,1,9,10,11,99,100,101 ?
Then rewrite in C.
Count is a mutable state, or the environment of the function. You can think of count as a second argument of that function.
The word static is also important.
 
Last edited:
Jose said:
Your analysis of the function is incorrect. Zero is the termination condition of that recursive function. Passing 0 will always return 0 and has to, otherwise you'd always recurse forever.

Integer division of 1 into 10 yields 0, so the function will recurse once and return 1+0 which is one. This is also true for the the digits 2-9.

Integer division of 10 into 10 yields 1, so the function with recurse twice and give you 1+1+0 =2. Same for digits 11-19.
Click to expand...
Alain De Vos said:
Is the java program ok ? If not fix first the java program.
Is the result ok for the unit tests as input 0,1,9,10,11,99,100,101 ?
Then rewrite in C.
Count is a mutable state, or the environment of the function. You can think of count as a second argument of that function.
The word static is also important. It tells when the memory for the variable is allocated and the initialization happens.
Click to expand...

Excuse me guys, it was a mistake on my part to explain this code without showing my non-recursive countdigits.

Java: 
public static byte countDigits(long num) {
 
     int i;
   
     if (num == 0)
            return 1;
   
     else {
     
      for (i=0; num!=0; i++) {
   
       num = num / 10;
 
     }
   
     }
   
           return (byte)i;
         
   }

I wanted to do the following code in the same way but recursively, I see that it is not possible.

In the first if, if num is 0, it returns 1. If it is greater than 0, it goes into the for, and I have a counter with the variable i.

I am counting digit by digit, divide with 10, if it were 10, then it would be 1, but it would enter the for. When splitting it again by 10, it would give a decimal result, but being a long they are lost, and there is already the for ending, returning my counter with the digits.

covacat said:
return num < 10 ? 1 : 1+countdigits(num/10)
Click to expand...

It works perfect, I see that it was not possible the way I was planning it.


Thanks guys.

Regards.

Edit:

With negative numbers it doesn't work, but I know why it is, but he didn't say anything about them, anyway.
 
C: 
#include <stdio.h>

int recursion(int i) {

   if(i > -10 && i < 10) {
      return 1;
   }
   return recursion(i / 10) + 1;
}

int  main() {
   int i = 123;
   printf("Number of Digits in %d is %d\n", i, recursion(i));
   return 0;
}
 
I did misunderstand your question. You're almost there. The first thing to notice is you don't need the count variable. Next notice that you don't have to special-case 0 in the recursive solution. Dividing 0 by 10 yields the same value as dividing 1 / 10 when you're doing integer division. So something like this:
Java: 
public static int countDigitsRecursive(int num)
{
        if((num / 10) == 0) return 1;
        return countDigitsRecursive(num / 10) + 1;
}

Here's a complete program with a test and a cleaned-up version of your iterative solution:
Java: 
public class Homework
{
    public static int countDigitsRecursive(int num)
    {
        int digits = num / 10;
        return digits == 0 ? 1 : countDigitsRecursive(digits) + 1;
    }

    public static int countDigitsIterative(int num)
    {
        if(num == 0) return 1;

        int i;
        for(i = 0; num != 0; i++)
        {
            num = num / 10;
        }

        return i;
    }

    public static void main(String[] args) throws Exception
    {
        int[] testDigits = new int[] {0,1,9,10,11,99,100,101,-1,-9,-10,-11,-99,-100,-101};

        for(int i = 0; i < testDigits.length; i++)
        {
            System.out.print(countDigitsRecursive(testDigits[i]));
            if(i < testDigits.length -1) System.out.print(",");
        }

        System.out.println("\n-----------------------------");

        for(int i = 0; i < testDigits.length; i++)
        {
            System.out.print(countDigitsIterative(testDigits[i]));
            if(i < testDigits.length -1) System.out.print(",");
        }
        System.out.println();
    }
}

Alain De Vos said:
Then rewrite in C.
Click to expand...
What for?
Alain De Vos said:
Count is a mutable state, or the environment of the function. You can think of count as a second argument of that function.
Click to expand...
The count variable is useless.
Alain De Vos said:
The word static is also important. It tells when the memory for the variable is allocated and the initialization happens.
Click to expand...
This is absolutely NOT what static means when applied to a Java method.
 
The count variable is not useless from a pedagogical point of view.
I thought wrongly the variable itself was on the heap, but,
stackoverflow.com

In Java, are variables declared inside static methods themselves static?

Assume the following: private static boolean A() { int parsedUntil = 0; ... ... ... } Is parsedUntil considered to be a static variable? I noticed that I can't declare it as static inside...
stackoverflow.com stackoverflow.com

As for the static function, according to wise stackoverflow,
Static methods (in fact all methods) as well as static variables are stored in the PermGen section of the heap, since they are part of the reflection data (class related data, not instance related). As of Java 8 PermGen has been replaced by MetaSpace and as per JEP 122 it only holds meta-data while static fields are stored in the heap.
 
Mostly true, all irrelevant.
The reason you declare methods static in simple code like this is so that you don't have to instantiate an object to get access to those methods. The object wouldn't have any state anyway. The difference between writing this:
Java: 
public class Homework
{
    public static int countDigitsRecursive(int num)
    {
        int digits = num / 10;
        return digits == 0 ? 1 : countDigitsRecursive(digits) + 1;
    }

    public static void main(String[] args) throws Exception
    {
        System.out.println(countDigitsRecursive( -10 ));
    }
}
And this:
Java: 
public class Homework
{
    public int countDigitsRecursive(int num)
    {
        int digits = num / 10;
        return digits == 0 ? 1 : countDigitsRecursive(digits) + 1;
    }

    public static void main(String[] args) throws Exception
    {
        System.out.println(new Homework().countDigitsRecursive( -10 ));
    }
}
Static methods are part of the class object in Java. They exist as soon as the class is loaded, and this happens before main() (or any other method) is called.

A variable in a static method is not a static variable. It will be allocated in the heap of every thread that enters the static method.
 
Agree, that was the reason.
I want to add if you need a static variable you need to define it outside the function to be in scope.
Note, following program works.
Code: 
class digits{
    int count(int x)
        {if (x==0) return 0;
                  else return (1+count(x/10));
    }
}
class Counter {
    public static void main(String[] args) {
            digits d=new digits();
        System.out.println(d.count(123));
        }
}
But if you move the class digits within Counter it will fail.
Code below fails.
Code: 
class Counter {
class digits{
    int count(int x)
        {if (x==0) return 0;
                  else return (1+count(x/10));
    }
}
    public static void main(String[] args) {
        digits d=new digits();
        System.out.println(d.count(123));
        }
}

The error given by the compiler is, counter.java:11: error: non-static variable this cannot be referenced from a static context digits d=new digits();
 
Jose The lesson is to use self calling function instead of using "for loop".
www.w3schools.com

W3Schools.com

W3Schools offers free online tutorials, references and exercises in all the major languages of the web. Covering popular subjects like HTML, CSS, JavaScript, Python, SQL, Java, and many, many more.
www.w3schools.com www.w3schools.com

With k > -10 && k < 10

Java: 
public class Main {
  public static void main(String[] args) {
    int result = Digits(-3123);
    System.out.println(result);
  }
  public static int Digits(int k) {
    if (k > -10 && k < 10) {
      return 1;
    } else {
      return Digits(k / 10) + 1;
    }
  }
}

With k!=0 this will not count the number of digits in the int

Java: 
public class Main {
  public static void main(String[] args) {
    int result = countDigitsRecursive(100);
    System.out.println(result);
  }
  public static int countDigitsRecursive(int k) {
    if (k != 0) {
      return countDigitsRecursive(k / 10) + 1;
    } else {
      return 1;
    }
  }
}


k=10
============
1 + sum(10 / 10)
1 + ( 1 + sum(1))
1 + ( 1 + ( 1 + sum(0) )
Result=3
Click to expand...

k=100
============
1 + sum (100/10)
1 + ( 1 + sum(10))
1 + ( 1 + ( 1 + sum(1) ) )
1 + ( 1 + ( 1 + ( 1 + sum(0) ) ) )
Result=4
Click to expand...

If you have the same task but without recursive then the method will be to cast the int into str and return it's length.
 
Alain De Vos said:
Agree, that was the reason.
I want to add if you need a static variable you need to define it outside the function to be in scope.
Click to expand...
More irrelevant nonsense. Now you're adding a non-static inner class instead of a method. The result is the same. You need an instance for non-static classes just like you do for non-static methods and variables if you want to access them in a static way.

None of this is in any way related to your statement "The word static is also important. It tells when the memory for the variable is allocated and the initialization happens." No. Memory allocation is implicit and opaque in Java. The keyword "static" is about how and where things can be accessed and has nothing to do with where it is in memory. Stop spreading nonsense about Java. It's clear you don't know what you're talking about.

VladiBG said:
Jose The lesson is to use self calling function instead of using "for loop".
Click to expand...
Re-read my first response in this topic.

VladiBG said:
Blah blah blah.
Click to expand...
Try my Java implementation. It's simpler than yours and works just as well. That approach will also work in C.
 
Behold, surrounded by his own aura of relevance, the god of Java has spoken. I pitty the man who holds that much knowledge in his life as he will always be surrounded by fools.
 
Guys, I want to thank you for all the responses. Keep doing my exercises.

I have terminated two recursive pow functions and everything seems to work fine, even with negative numbers:

Java: 
public static double power10Recursive(int exp) {
    
     if (exp == 0) return 1;
     if (exp <  0) return 1 / (10 * power10Recursive(Math.abs(exp + 1)));
     else return 10 * power10Recursive(exp - 1); 
  
    
    }
  
    public static double powerRecursive(double base, int exp) {
    
     if (exp == 0) return 1;
     if (exp <  0) return 1 / (base * powerRecursive(base, Math.abs(exp + 1)));
     else return (base * powerRecursive(base, exp - 1)); 
  
    
    }

I am going to continue with a fibonacci function, I have the following:

Java: 
public static String fibonacciSerie(long max) {
  
    BigDecimal a = BigDecimal.ZERO;
    BigDecimal b = BigDecimal.ONE;
  
    System.out.print("Fibonacci numbers: " + a + " " + b);
  
       for (; b.add(a).compareTo(BigDecimal.valueOf(max)) == -1 ;) {
  
        a = a.add(b);
    
       System.out.print(" " + a);
    
      if (b.add(a).compareTo(BigDecimal.valueOf(max)) == 1)
        break;
    
        b = a.add(b);
      
       System.out.print(" " + b);
    }
    
       return a + " " + b;
  
}

I'm going to go for it, I have to do this function but recursively.

P.D: I'm an ASM guy, I'm a fan and I've never had to build recursive codes, I still don't understand what advantage a for recursion has.

My teacher told us that it is for optimization, I thought WTF !!, you are doing this (num / 10) using operators such as division is super slow and expensive for the CPU.

When I'm done, I'll propose an ASM solution for the countdigits, but with bit-level comparisons, I think it can be done and it's a lot better than dividing by 10.

Regards.

P.S2:

Yes, the return is silly, I have to return a string, since I have to use the last two numbers to make the "golden ratio", and I have to pass them as a string because I do not explain the arrays and I am forbidden to use them ... I have the following. So they can see it:

Java: 
public static BigDecimal goldenRatio(BigDecimal a, BigDecimal b) {
 
  return max(a,b).divide(min(a,b), 100, RoundingMode.UP);
   
}


String decimal = fibonacciSerie(dataEntryLong("Enter max number: "));
         
         Scanner deci = new Scanner(decimal);
       
         BigDecimal a = new BigDecimal(deci.next());
         BigDecimal b = new BigDecimal(deci.next());
                 
         
         System.out.println("\n\n\nDiv: " + goldenRatio(a,b));

Anyway.
 
I haven't followed this topic, but reading your last post about the reason for recursive functions: well it's more of an academic exercise than anything else. Dah! With small functions it can be more readable. With larger functions it can be a nightmare to read. Your code might look more compact but if there's a bug in it, recursiveness often makes it very hard to determine.

Overall, these types of functions are slower as they wind on/wind off from the stack and just plain dumb in all but a minor amount of cases. It's pretty easy with an out-of-control recursive function to eat up your allocated stack space. For some easy reading see wikipedia. However, I'm not sure how Java deals with functions, they might not use a function stack like C does, for example.

You can undoubtedly write faster and better code in Java (something I thought I'd never say) not using recursive functions.

Do them for your homework and exams, then forget about them in your professional career; something nice to know but never/rarely use. ;)
 
Well, it depends, for example Scala simultaneously has a @tailrec annotation and not enough syntactic constructs for proper C-style loops, so performance and readability balances out.

As for the advice to the OP: 1. learn to format your code properly; 2. don't ever listen to people who can't format their code (or sentences for that matter).
 
Jose said:
The keyword "static" is about how and where things can be accessed and has nothing to do with where it is in memory.
Click to expand...
Te be precise, static dispatch is an opposite of dynamic dispatch. That's the most likely etymology here.
 
shkhln said:
Well, it depends, for example Scala simultaneously has a @tailrec annotation and not enough syntactic constructs for proper C-style loops, so performance and readability balances out.

As for the advice to the OP: 1. learn to format your code properly; 2. don't ever listen to people who can't format their code (or sentences for that matter).
Click to expand...

PS: A tail-call factorial using an accumulator:
Code: 
public static TailCall<Integer> factorial(int fact, int n) {
    if (n == 1) {
        return TailCalls.done(fact);
    }

    return () -> factorial(fact * n, n-1);
}
 
shkhln said:
Te be precise, static dispatch is an opposite of dynamic dispatch. That's the most likely etymology here.
Click to expand...
I suppose there is an analogy with c++ classes.
Note : one must be careful. Sometimes a word in one programming language has another definition of the same word used in a different programming language.
 
Alain De Vos said:
PS: A tail-call factorial using an accumulator:
Code: 
 TailCall<Integer>
Click to expand...
That's some weird shit. A roughly idiomatic Scala version looks something like this:
Code: 
import scala.annotation.tailrec

def factorial(n: Int): Int = {

  @tailrec
  def iter(n: Int, res: Int): Int = if (n == 1) res else iter(n - 1, res * n)

  iter(n, 1)
}
 
I hope the OP doesn't mind, but this is non-tail recursive fibonnaci in Kotlin,
Code: 
fun fibo(x: Int):Int{
        if (x<2) return x
        else return (fibo(x-1)+fibo(x-2))
}
fun main(args: Array<String>) {
val x = 42
val y = fibo(x)
print("$x \n")
print("$y \n")
}

And a tail-recursive one,
Code: 
@JvmOverloads
tailrec fun fibo(n: Int, a: Int = 0, b: Int = 1): Int =
    when (n) {
        0 -> a
        1 -> b
        else -> fibo(n - 1, b, a + b)
    }
fun main(args: Array<String>) {
val x = 42
val y = fibo(x)
print("$x \n")
print("$y \n")
}
 
Alain De Vos said:
As if everything on stackoverflow is weird ?
Click to expand...
It's only weird 'cause you didn't paste all of it. Here's the missing piece:

Java: 
@FunctionalInterface
public interface TailCall<T> {
    TailCall<T> apply();

    default boolean isComplete() {
        return false;
    }

    default T result() {
        throw new Error("not implemented");
    }

    default T get() {
        return Stream.iterate(this, TailCall::apply).filter(TailCall::isComplete)
                                                .findFirst().get().result();
    }
}
Therefore tail call = iteration. Fantastic! That is so much clearer than
Java: 
public static int countDigitsIterative(int num)
    {
        if(num == 0) return 1;

        int i;
        for(i = 0; num != 0; i++)
        {
            num = num / 10;
        }

        return i;
    }
Functional = doing the same shit with far more and more obscure code.
 
You must log in or register to reply here.
Back
Top