Other count digits recursive

Alain De Vos

Son of Beastie

Reaction score: 869
Messages: 2,826

Functional = doing the same shit with far more and more obscure code. As a generalization that can count. I had not expect less.
But to be honest, i don't like streams to solve simple problems. I don't see the need.
 

shkhln

Daemon

Reaction score: 1,062
Messages: 2,390

That's 'cause it's a straight copy-paste out of Stackoverflow:

No, I know what it is (Scala actually has a similar helper in stdlib). I can't be scared that easily — I've seen iteratees. What I mean is that without compiler/runtime support this just amounts to pissing against the wind.
 

Alain De Vos

Son of Beastie

Reaction score: 869
Messages: 2,826

A java tail-recursive version, without the use of streams nor iterators. It's not functional as you don't really pass functions to functions.
Code:
class fibo{
    public static void main (String[] args){
        System.out.println(fib(42,0,1) );
    }
    static int fib(int n, int a, int b ){
        if (n==0) return a;
        else if (n==1) return b;
        else return fib(n - 1, b, a + b);
    }
}
 

Jose

Daemon

Reaction score: 1,153
Messages: 1,368

No, I know what it is (Scala actually has a similar helper in stdlib). I can't be scared that easily — I've seen iteratees. What I mean is that without compiler/runtime support this just amounts to pissing against the wind.
I think we're in vigorous agreement. Without compiler/runtime support this is just an awkward and obscure way of turning recursion into iteration.

I believe there are no recursive solutions that can't be re-written in an iterative form, and that the iterative form is usually more efficient. So yeah, recursion is mainly a learning exercise.
 

Jose

Daemon

Reaction score: 1,153
Messages: 1,368

A java tail-recursive version, without the use of streams nor iterators. It's not functional as you don't really pass functions to functions.
Code:
class fibo{
    public static void main (String[] args){
        System.out.println(fib(42,0,1) );
    }
    static int fib(int n, int a, int b ){
        if (n==0) return a;
        else if (n==1) return b;
        else return fib(n - 1, b, a + b);
    }
}
A lightly edited version of code from here:

What's hilarious about this particular plagiarism is that function is NOT tail-recursive(EDIT: in Java, as Shkhln points out below). You could've found this out easily if you had actually understood the Stackoverflow answer you plagiarized earlier. Modify the code like this
Java:
class fibo {
    public static void main (String[] args){
        System.out.println(fib(42,0,1) );
    }
    static int fib(int n, int a, int b ){
        if (n==0) return a;
        else if (n==1) {
            Thread.dumpStack();
            return b;
        }
        else return fib(n - 1, b, a + b);
    }
}
And you'll get output like this

Code:
java.lang.Exception: Stack trace
    at java.base/java.lang.Thread.dumpStack(Thread.java:1383)
    at scratch.fibo.fib(fibo.java:10)
    at scratch.fibo.fib(fibo.java:13)
    at scratch.fibo.fib(fibo.java:13)
    at scratch.fibo.fib(fibo.java:13)
    at scratch.fibo.fib(fibo.java:13)
...
There are exactly 42 calls to fib(), as you would expect for a non-tail recursive solution.
 

astyle

Daemon

Reaction score: 748
Messages: 1,626

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;

}
Shouldn't your long be an int? Java has a tendency to complain about number type mismatches. Oh, and most recursive problems usually have an initial pattern specified, that sometimes has to be taken care of as a special case in code.
 

Alain De Vos

Son of Beastie

Reaction score: 869
Messages: 2,826

Good point. So if i'm correct you should hint the java compiler by using iterators that tail-call optimisation is possible.
 

Jose

Daemon

Reaction score: 1,153
Messages: 1,368

I'll be back. Must first measure times spend.
What's wrong? A quick and dirty Google search is not working? Let me save you some time. The Java compiler has no such feature, as Shkhln has already mentioned several times. You were once again spouting nonsense about Java when you said:
Good point. So if i'm correct you should hint the java compiler by using iterators that tail-call optimisation is possible.
What's it gonna take to get you to stop spreading nonsense and half-digested random crap you found on the Internet?
 

Jose

Daemon

Reaction score: 1,153
Messages: 1,368

This is a tail-recursive function, but since there is no tail-call optimization in Java it is not being transformed in a loop.
So have the compiler turn it into something like this:
Java:
class TailFibonacci {
    public static void main (String[] args){
        System.out.println(fib(9,0,1) );
    }
    static int fib(int fibo, int twoBack, int oneBack ){
        while(true) {
            int temp;
            if(fibo == 0) return twoBack;
            if(fibo == 1) return oneBack;
            fibo--;
            temp = twoBack;
            twoBack = oneBack;
            oneBack += temp;
        }
    }
}
That is much simpler in languages that support labels and goto:

EDIT: But it still boils down to iteration. It's just the compiler is hiding it for you now so you don't offend the high priests of Functional who have declared iteration is evil and unclean.
 

astyle

Daemon

Reaction score: 748
Messages: 1,626

EDIT: But it still boils down to iteration. It's just the compiler is hiding it for you now so you don't offend the high priests of Functional who have declared iteration is evil and unclean.
UNIX is not a religion. Neither is programming. Yeah, we have schools of thought that different designs follow - and all of them have their pluses and minuses that have their fans and detractors. So why bother getting worked up over something the cat dug up from the ground anyway?
1638819292745.png
 

Alain De Vos

Son of Beastie

Reaction score: 869
Messages: 2,826

So have the compiler turn it into something like this:
Java:
class TailFibonacci {
    public static void main (String[] args){
        System.out.println(fib(9,0,1) );
    }
    static int fib(int fibo, int twoBack, int oneBack ){
        while(true) {
            int temp;
            if(fibo == 0) return twoBack;
            if(fibo == 1) return oneBack;
            fibo--;
            temp = twoBack;
            twoBack = oneBack;
            oneBack += temp;
        }
    }
}
That is much simpler in languages that support labels and goto:

EDIT: But it still boils down to iteration. It's just the compiler is hiding it for you now so you don't offend the high priests of Functional who have declared iteration is evil and unclean.
One can not ignore java compiler sometimes behaves in a stupid way and is not capable of recognizing possible tail-recursion.
I'll come back later. But first i must measure time.
 
OP
F

freejlr

Member

Reaction score: 9
Messages: 41

Shouldn't your long be an int? Java has a tendency to complain about number type mismatches. Oh, and most recursive problems usually have an initial pattern specified, that sometimes has to be taken care of as a special case in code.
Works, this is how I have written the exercise, I have to do the same. I am using Dr Java at no time did he warn me.

But apparently if I declare a variable and don't initialize it, if I get error 😆

Java:
int i;

//Apparently he does not like that I declare a variable and do not initialize it with a value.
//It would give me an error

int i = 0;

//This is what you want to see, that it gives it a value, but in theory when declaring a variable its value is already zero, why would it have to initialize at 0?
//I don't know about Java or Dr java, I still don't understand ...

Guys, I've been thinking about a count digit in ASM, but it seems it's being harder for me than I thought.

I have thought of using bsr and bsf, example:

Code:
.section .text
.globl _start

_start:

movq $0x8000000000000010, %rbx
bsfq %rbx, %rdi    // rdi = 4 index bit
bsrq %rbx, %rsi    // rsi = 63 index bit

I have been thinking about knowing where the bits of the number end, for example if bsr gives me the index 31 0 30 I know that the number is 10 digits since the maximum number of an unsigned int is 4294967295

But of course, calculating the 10,1000,10000 is more complicated, it can be done but it is more complicated than it seems.

I am still thinking about my fibonacci exercise, I do not pretend that my exercises do much less but I do not understand this, the explanation by my teacher is practically zero.

He does not say how he wants the codes and of course, you have to interpret what he wants to see.

/* Write the first 100 numbers of the Fibonacci serie
* @param n the number of numbers of the serie of Fibonacci
* 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, ... */

public void writeFibonacci(long n)

That's all I have, the problem I see is that being void I will have to use a variable, right?

Global, I will have to use n as a counter until reaching 100 numbers, I really don't understand why it puts n if they are the first 100 numbers, the value is fixed, for a variable n? It could be used to increase the numbers to be displayed or to minimize them.

What would be the path to take? As I said, I do not pretend that the tasks give me, but it is what occurs to me to create two global variables with the two default numbers BigDecimal.ONE and ZERO and from there show the numbers and add the sequence and save them in those variables, as I have in my iterative code.

But of course if I want to call the function again in the main, after seeing the function called, I have to initialize the variables to 0 and 1 again, since they will be written with the values from before.

These are all the functions that I had to create, in my exercises, apparently they all work well, ask a colleague and apparently they don't need to work with zero and negative numbers, anyway

Java:
public static int countDigitsRecursiva(long num) {   
    
            
          if(num > -10 && num < 10) return 1;
          else return 1 + countDigitsRecursiva(num / 10); 
            
 
} 


public static int ocurrencesRecursiva(long num, int digitc, int c)
{
  
    if (num == 0 && c == 0) return 1;
    else if (num == 0) return 0;
    
    if (num % 10 == digitc) return 1 + ocurrencesRecursiva(num / 10, digitc, c + 1);
    return ocurrencesRecursiva(num / 10, digitc, c + 1);
    
}
  
    
    public static double power10Recursive(int exp) {
      
     if (exp == 0) return 1;
     if (exp <  0) return 1 / (10 * power10Recursive(-(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));   
    
      
    }

Thanks guys.
 
OP
F

freejlr

Member

Reaction score: 9
Messages: 41

Hi guys, I already have the code, it seems somewhat crappy but it works, since in the advert it says to print the first 100 numbers.

I wanted to make the user enter the numbers to be displayed in n, but it works badly with odd numbers since I am printing two numbers at the same time, surely it has a solution but with this the exercise would be solved.

Java:
  public static void writeFibonacci(long max) {
    
    if (max <= 0) {
      
      return;
      
    }
    
        System.out.print(a + " ");
        a = a.add(b);
        System.out.print(b + " ");
        b = a.add(b);
        writeFibonacci(max-1); 
        
}

As I said, I had to declare two local variables a and b, to store the sum of the two variables. The method being void does not return anything and I think that is the only way, right?

Java:
//Global variables

public static BigDecimal a = BigDecimal.ZERO;
public static BigDecimal b = BigDecimal.ONE;

//Calling the method in the menu

case 3:
BigDecimal a = BigDecimal.ZERO;
BigDecimal b = BigDecimal.ONE;
         writeFibonacci(50L);
         break;

I have to assign the values in the case again, because if the user wants to execute the method again, he will have the values of the previous execution.

I pass a 50, since in the method two values are printed, 50 x 2, the first 100 fibonacci numbers.

I don't like the solution, but reading your comments about recursion, and the little importance that my teacher will give it, I think it's okay.

Sure you could do a lot better.

Regards.
 

astyle

Daemon

Reaction score: 748
Messages: 1,626

In my programming classes in college, the important thing was that the code compiles, runs, and outputs verifiably correct information. Readability of the code was secondary, but still important - no spaghetti code, and no 'GO TO' - that one was grounds for failing the assignment. Correct implementation (be it recursion or a different programming paradigm) - that was important in some classes/courses, but not others.
 

Alain De Vos

Son of Beastie

Reaction score: 869
Messages: 2,826

It is possible to create a lazy evaluated infinite list of fibonnaci numbers, where to last member of the list is in fact a function call.
 

covacat

Daemon

Reaction score: 515
Messages: 1,040

In my programming classes in college, the important thing was that the code compiles, runs, and outputs verifiably correct information. Readability of the code was secondary, but still important - no spaghetti code, and no 'GO TO' - that one was grounds for failing the assignment. Correct implementation (be it recursion or a different programming paradigm) - that was important in some classes/courses, but not others.
we wrote COBOL programs which nobody actually punched on cards and nobody cared if they actually worked :)
 

Alain De Vos

Son of Beastie

Reaction score: 869
Messages: 2,826

This Clojure version is interesting,
Code:
(def fib-seq-seq
  ((fn fib [a b]
     (lazy-seq (cons a (fib b (+ a b)))))
   0 1))
(take 30 fib-seq-seq)
 

shkhln

Daemon

Reaction score: 1,062
Messages: 2,390

Still fascinated by this one? Even Java can do this now:

% scala
Welcome to Scala 2.13.1 (OpenJDK 64-Bit Server VM, Java 11.0.12).
Type in expressions for evaluation. Or try :help.

scala> import java.util.stream._
import java.util.stream._

scala> IntStream.rangeClosed(1, 30).reduce(1, (x, y) => x * y)
res0: Int = 1409286144


(I'm using Scala REPL simply because it's more convenient.)
 

shkhln

Daemon

Reaction score: 1,062
Messages: 2,390

Although, to be fair, an actual lazy sequence of factorials would require a custom Int stream generator. There are not enough built-in methods to easily construct one.
 

Alain De Vos

Son of Beastie

Reaction score: 869
Messages: 2,826

For a java only version i must dig a bit deeper. Because there is a multitude of libraries/classes.
The output of an operator in one library cannot be used as input for a function in other library etc...
 
Top