Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[TheBiggerFish]

@DragonDePlatino:

So:How to write a recursive Fibonacci number calculator.

Code: [Select]

//Declared outside the method because it'd be silly to recreate it every call
int tmp = 0;
public static int fibRecurse(int old, int new, int depth){
    if(depth == 0){System.out.println(old+new);
    else{
        System.out.println(old+new);
        tmp=old+new;
        old=new;
        new=tmp;
        depth--;
        fibRecurse(old, new, depth);
    }
}Which is not actually complicated.

You call it from main, with 1, 1, and your preferred number of numbers.  It's really a glorified for loop like this.

That is legitimately terrible if a textbook is telling you to "not think about it" when trying to implement something. God forbid they ever try to explain the Tower of Hanoi recursive solution.

And yeah, the textbook should never not explain something at all if they want you to do it.

[EnigmaticHat]

Recursive functions are a structure, same as a for or while loop.  Think of them as a graph where each function call is a point with lines from parent to child.  So if each call can call four more functions, its like a tree graph.  If each call can only call itself once, its like a line.  Or at least that's how I like to think of it.

I dunno, they're not that scary once you grasp the concept, and its very stupid that your textbook explained them that way.  Its like a loop with more control, flexibility, and exciting opportunities to instantly call the same function an infinite number of times by accident.

[itisnotlogical]

My first experience with recursion is when I was first learning C# and didn't realize that get/set methods would call themselves infinitely if you didn't have a private variable they could change without calling get/set again.

[LoSboccacc]

That is legitimately terrible if a textbook is telling you to "not think about it" when trying to implement something. God forbid they ever try to explain the Tower of Hanoi recursive solution.

Yeah I have to work with a guy that grew up on that  bullshit, watching him work is super painful. He never stops to collect the dots and think up a solution, instead copies code pattern from everywhere, hammers them into place and keep adding/replacing random snippets until something works

It's like watching a bad pathfinder doing an exhaustive search.

[itisnotlogical]

How do you accomplish anything like that? Is it really possible to finish something by just looking up and using other people's code like that?

[LoSboccacc]

yes, it's possible to get some very specific output out of a system, but there are many, many downsides. often the result is three pieces of code badly intermingled, and nobody knows how or why it works.

imagine calling in a library random until the output you want is there - at which point which call did what you wanted? most of the resulting code only covers success cases, of course, any unforeseen, different or badly timed input can crash the code anytime.

[Antsan]

[…]
I hate recursion.

Hate the textbook instead. The recursive definition for the fibonacci function is really straightforward: The first two fibonacci numbers are defined as 1 and 1 (or "1 and 2" or "0 and 1", depending on who you ask), every following fibonacci number is defined as the sum of the previous two.
So there are three cases for any given fibonacci number (I don't know Java syntax, so have some pseudo code instead):

Code: [Select]

fibonacci ( n ) =
  if n = 0
     ...
  else if n = 1
     ...
  else
     ...
In the first two cases (which are the first two fibonacci numbers) we can just return the known fibonacci number:

Code: [Select]

fibonacci ( n ) =
  if n = 0
     1
  else if n = 1
     1
  else
     ...
And in the last case, we just compute the previous two fibonacci numbers and add them together, since that is exactly how fibonacci numbers are defined:

Code: [Select]

fibonacci ( n ) =
  if n = 0
     1
  else if n = 1
     1
  else
     fibonacci(n-1)+fibonacci(n-2)
And that's it. There's no black magic, it's not hard to think about, just translating the definition of fibonacci numbers into whatever programming language you are using.
If your textbook tells you "don't think about it!", it's not because the problem is hard, but probably rather because the people writing the book didn't put in the effort of explaining recursion.

Of course the given definition can be simplified (by combining the first two branches) and made more robust (by checking only n<=1), but that's got nothing to do with recursion, so I left it out.

[alexandertnt]

That is legitimately terrible if a textbook is telling you to "not think about it" when trying to implement something. God forbid they ever try to explain the Tower of Hanoi recursive solution.

Yeah I have to work with a guy that grew up on that  bullshit, watching him work is super painful. He never stops to collect the dots and think up a solution, instead copies code pattern from everywhere, hammers them into place and keep adding/replacing random snippets until something works

It's like watching a bad pathfinder doing an exhaustive search.

I have come across some programmers like that. If their program doesn't work, they move bits of code around or add/remove lines for no real purpose until the result looks "closer" to being correct, they don't seem interested in understanding how their program is currently functioning, and they don't even seem to fully understand the problem they are trying to solve.

It's very frustrating.

[miauw62]

@DragonDePlatino:

So:How to write a recursive Fibonacci number calculator.

Code: [Select]

//Declared outside the method because it'd be silly to recreate it every call
int tmp = 0;
public static int fibRecurse(int old, int new, int depth){
    if(depth == 0){System.out.println(old+new);
    else{
        System.out.println(old+new);
        tmp=old+new;
        old=new;
        new=tmp;
        depth--;
        fibRecurse(old, new, depth);
    }
}Which is not actually complicated.

You call it from main, with 1, 1, and your preferred number of numbers.  It's really a glorified for loop like this.

That's the more efficient, O(N) implementation. Generally, for Your First Recursive Function(TM), you're supposed to write something like

Code: [Select]

int fib(int n)
{
    if(n == 0)
    {
        return 0;
    }
    if(n == 1)
    {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}
but obviously that is O(N^2) which is pretty bad.

Then again, considering how quickly the Fibonacci sequence exceeds INT_MAX, it's usually pretty reasonable to use an O(1) implementation, that being an array with the values.

[Mephisto]

Code: [Select]

Your First Recursive Function(TM)

but obviously that is O(N^2) which is pretty bad.

One upside to this version is that it's also trivially memoizable. My university didn't cover memoization (don't ask me why, I implemented it on my own). I think it would have been valuable, however, to have these two topics back-to-back.

1) How many times do you calculate fib(2) while you're looking for fib(100)? (tip: the number of calls can't be represented by an unsigned 64 bit integer)
2) Hmm... All but one call will go away if we keep that value around somewhere.

[TheBiggerFish]

@miauw:I never would have thought someone would write that other example, good grief.  :v

[Putnam]

but obviously that is O(N^2) which is pretty bad.

I'm pretty sure that, if you follow the whole tree, you'll find that it's equal to the fibonacci function in terms of runtime; in other words, its asymptotic growth is closer to O(φ^n).

[MagmaMcFry]

Here's the obligatory O(log(n)) implementation:

Code: (Lua) [Select]

function fib(n)
local f, g = 1, 0
local a, b = 0, 1
while n > 0 do
if n % 2 == 1 then
f, g = a*f+b*g, a*g+b*f+b*g
n = n - 1
end
a, b = a*a+b*b, 2*a*b+b*b
n = n/2
end
return g
end


[Putnam]

Code: [Select]

function fib(n)
    local root=math.sqrt(5)
    local phi=(1+root)/2
    local invphi=phi-1
    return (phi^n-(-invphi)^n)/root
end

tbh i'm not sure what the actual complexity of that is... it could be said it's O(1), but that relies on division and exponentiation being O(1)

[DragonDePlatino]

God forbid they ever try to explain the Tower of Hanoi recursive solution.

Oh no... No... NOOOOOOOOO!

Recursive functions are a structure, same as a for or while loop.  Think-

And stop right there! I think that's exactly what I was looking for. Recursive functions aren't these massively intimidating things, they're just another kind of loop. You have a base case, the self-call and a return. That's a huge oversimplification but it's a good way for me to understand it. Thanks.

And that's it. There's no black magic, it's not hard to think about, just translating the definition of fibonacci numbers into whatever programming language you are using.

Yup! That's the solution we arrived at almost line-for-line. Thanks for the step-by-step clarification.

Oh yes, and good news everyone! Today we had a timed online quiz and guess what showed up? Recursiooooon! Our task was to find the max in an ArrayList of floats without static variables or loops. Trivially simple for someone with minimal programming experience, but a bit difficult for me. Thankfully, the help from this thread helped me organize my thoughts. Everything smoothly compiled without any syntax errors or stack overflows.

Code: [Select]

import java.util.*;

class Main {
static Float maxElem(ArrayList<Float> elems)
{
if (elems.size() == 1)
return elems.get(0);
else if (elems.get(0) > elems.get(elems.size() - 1))
elems.remove(elems.size() - 1);
else
elems.remove(0);

return maxElem(elems);
}
public static void main(String[] args)
{
ArrayList<Float> floats = new ArrayList<Float>();
Random rand = new Random();

for (int i = 0; i < 10; ++i)
floats.add(rand.nextFloat() * (100 - 1) + 1);

    System.out.print("Input numbers:\n" + floats + "\nMaximum: " + maxElem(floats));
  }
}
I'm still learning to crawl when it comes to programming, but I'm really proud of how much better I did this time.