[SOLVED]

[short]

Here's a suggestion. Grab a piece of paper and pencil. Sit down and pick a number n, such as 4 or 5, 5 is good, and try and follow the code on paper. A lot of times trying to understand a complex idea is best solved by sitting down and trying to trace what is happening on paper and pencil.

[avansc]

recursion is a bitch at best of times.

okay..
so we know what fib(1) = 1 and fib(2) = 1
so fib(3) = fib(1)+fib(2) = 1+1 = 2
so next we know that fib(4) = fib(2) + fib(3)
thus fib(4) = fib(2) + fib(1) + fib(2) = 1 + 1 + 1 = 3
sooo... fib(5) = fib(3) + fib(4)
thus fib(5) = fib(1)+fib(2) + fib(2) + fib(3)
thus fib(5) = fib(1)+fib(2) + fib(2) + fib(1) + fib(2) = 1+1+1+1+1 = 5

and so the cycle goes. its just adding one everytime. its actually very inefficient.

i hope that explained it a little better.

[avansc]

okay so here is a java program that might help a little.

Code: Select all

//
//  fib.java
//  fib
//
//  Created by avansc on 7/29/09.
//  Copyright (c) 2009 BrOkEnBiT. All rights reserved.
//
import java.util.*;
import java.util.StringTokenizer;

public class fib {
	
	static public int pass(String data)
	{
		StringTokenizer st = new StringTokenizer(data,"+");
		
		while(st.hasMoreTokens())
		{
			if(Integer.parseInt(st.nextToken()) > 2)
				return 0;
			
		}
		return 1;
	}
	
	static public String split(String data)
	{
		StringTokenizer st = new StringTokenizer(data,"+");
		String temp = "";
		String ret = "";
		
		int a = 0;
		int b = 0;
		
		while(st.hasMoreTokens())
		{
			temp = st.nextToken();
			if(Integer.parseInt(temp) < 3)
			{
				ret += temp + "+";
			}else{
				a = Integer.parseInt(temp)-2;
				b = Integer.parseInt(temp)-1;
				ret += a+"+"+b+"+";
			}
		}
		return ret.substring(0, ret.length()-1);
		
	}
	
    public static void main (String args[])
	{
		String fib = "8";
		System.out.println(fib);

		while(pass(fib) != 1)
		{
			fib = split(fib);
			System.out.println(fib);
		}
        StringTokenizer st = new StringTokenizer(fib,"+");
		System.out.println(st.countTokens());
    }
}

output.

8
6+7
4+5+5+6
2+3+3+4+3+4+4+5
2+1+2+1+2+2+3+1+2+2+3+2+3+3+4
2+1+2+1+2+2+1+2+1+2+2+1+2+2+1+2+1+2+2+3
2+1+2+1+2+2+1+2+1+2+2+1+2+2+1+2+1+2+2+1+2
21

so thats what happens to fib(8) and 1 and 2 are equal to 1. so you just count the terms. and fib(8) = 21

[jtst1]

okay so here is a java program that might help a little.

Code: Select all

//
//  fib.java
//  fib
//
//  Created by avansc on 7/29/09.
//  Copyright (c) 2009 BrOkEnBiT. All rights reserved.
//
import java.util.*;
import java.util.StringTokenizer;

public class fib {
	
	static public int pass(String data)
	{
		StringTokenizer st = new StringTokenizer(data,"+");
		
		while(st.hasMoreTokens())
		{
			if(Integer.parseInt(st.nextToken()) > 2)
				return 0;
			
		}
		return 1;
	}
	
	static public String split(String data)
	{
		StringTokenizer st = new StringTokenizer(data,"+");
		String temp = "";
		String ret = "";
		
		int a = 0;
		int b = 0;
		
		while(st.hasMoreTokens())
		{
			temp = st.nextToken();
			if(Integer.parseInt(temp) < 3)
			{
				ret += temp + "+";
			}else{
				a = Integer.parseInt(temp)-2;
				b = Integer.parseInt(temp)-1;
				ret += a+"+"+b+"+";
			}
		}
		return ret.substring(0, ret.length()-1);
		
	}
	
    public static void main (String args[])
	{
		String fib = "8";
		System.out.println(fib);

		while(pass(fib) != 1)
		{
			fib = split(fib);
			System.out.println(fib);
		}
        StringTokenizer st = new StringTokenizer(fib,"+");
		System.out.println(st.countTokens());
    }
}

output.

8
6+7
4+5+5+6
2+3+3+4+3+4+4+5
2+1+2+1+2+2+3+1+2+2+3+2+3+3+4
2+1+2+1+2+2+1+2+1+2+2+1+2+2+1+2+1+2+2+3
2+1+2+1+2+2+1+2+1+2+2+1+2+2+1+2+1+2+2+1+2
21

so thats what happens to fib(8) and 1 and 2 are equal to 1. so you just count the terms. and fib(8) = 21

That I do not understand. I don't know java. Barley c++ aparently lol. I understand how the series works, but not the code if that makes sense.

Code: Select all

   cout << "Processing fib)" << n << ")...";
   if (n < 3)
   {
      cout << "Return 1!\n";
      return(1);
   }
   else
   {
      cout << "Call fib(" << n-2 << ") and fib(" << n-1 << ").\n";
      return( fib(n-2) + fib(n-1));

none of that makes sense, or how I would use that in the future.

[avansc]

okay different approach..

fib(n) will always return 1 unless n > 2. and if n greater than 2 it subtracts 2 and 1 and calls it self with those values.

everytime fib(n) is called. the return 1 will be called. and since its + it just adds the number of times fib was called.

[jtst1]

okay different approach..

fib(n) will always return 1 unless n > 2. and if n greater than 2 it subtracts 2 and 1 and calls it self with those values.

everytime fib(n) is called. the return 1 will be called. and since its + it just adds the number of times fib was called.

ok it makes sense that it will always return 1 if n < 2 because the first 2 numbers are 1. But what had me was it subtracts 2 and 1 so essentially 3, why doesn't it turn out negative?
I really appreciate you helping me with this. I feel like I can't move on unless I understand this

[dandymcgee]

The blank was for a number any number. How does it know that 8 is the 6th number in the fib series? or 10 is some other number in the series.

What you refer to as "blank", mathmeticians refer to as "n" (or "x" or whatever letter or symbol they please really, it's similar to how you can name your variables in C++ whatever you'd like). See Below.

I would like to understand what the code does, like the n-2+n-1 I don't understand what n is, and F

In algebra we often replace an unknown value with a variable (often in the form of a letter, "n" in this case).

In the mathematical equation, I believe F stands for the Fibonacci sequence and the n stands for a value representing a place in the sequence (ie. "F3" would mean the third value in the Fibonacci sequence).

If you refer to avansc' explanation you see that:

fib(3) = fib(1)+fib(2)
OR
fib(3) = fib(3-2) + fib(3-1)
OR
(replacing 3 with "blank" (more commonly known as "n"))
fib(n) = fib(n-2) + fib(n-1)

Hence the equation you see in the C++ code. Now both fib(2) and fib(1) will return a value of 1 (because both the first and second numbers in the Fibonacci sequence are 1) and therefore fib(3) will return (1 + 1) or 2.

If you called fib(4), when it returned it would call fib(4-2) + fib(4-1) OR fib(2) + fib(3).

Since we know fib(2) will always return 1, and we just discovered that fib(3) will return 2, we can safely assume fib(4) will return the sum or these two functions' return values: 1 + 2 = 3.

I know I'm the eighth person to try to explain this, but I hope I helped add a little to your understanding.

ok it makes sense that it will always return 1 if n < 2 because the first 2 numbers are 1. But what had me was it subtracts 2 and 1 so essentially 3, why doesn't it turn out negative?

No, it does not subtract three.

Nowhere does it subtract 1 from the value of n, (that would require a n = n-1, n -=1, or n-- call to be made).
It's simply passing a value to another iteration of itself equivalent to n-1 without ever altering the memory storing n's value.

Keep in mind with recursion there are many different instances of the same function happening at the same time. There is a different memory location for each function call to store it's respective "n" value, and no function alters any other function's "n". When the function returns, its "n" value goes out of scope, and that memory is free to be used by whatever else needs to use it.

[jtst1]

I'm trying to understand this so hard, but it's just not clicking. I understand the series, and how it works. I understand that everytime it returns 1 it adds them all together to get the nth number in the series. I just can't make sense of the code, and thank you dandymcgee, you helped me understand more. I think i'm going to have to wait and ask a teacher at school. I'm really bad at understanding things via text/over the comp.

I understand what variables are, and understand algebra. I'm going into algebra 2, I just haven't had anything like this that I can understand how it works, but not the internals that make it work.. If that makes sense.

[Falco Girgis]

Y'know, I honestly don't blame you. Recursion was a bitch for me too when I first started. Don't be too hard on yourself, bro.

[jtst1]

Yeah I understand most of it, so I think i'm going to move on and come back to it later. Thank you everyone for the help :P

Yo Falco how goes the Elysian shadows revolution?

[Falco Girgis]

Working on getting Episode 2 out in the next few weeks.

...working our asses off.

[wearymemory]

You're trying to get the nth number in the Fibonacci Sequence. Fn = f(n-1) + f(n-2), therefore fn is a composition of each number before it, so in order for the program to get that number, the program needs to make up each of those Fibonacci numbers, and that is what it is doing.

An easier way of understanding how it goes about doing this, is knowing what seeds the Fibonacci sequence, and how those other numbers are created. This example does not use recursion, it stores the values inside of a vector, and f40 takes less time to process.

Code: Select all

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int f = 0, g = 1;
    for (int i = 2; i <= 40; i++) {
        f = f + g;
        g = f - g;
        printf("f%d = %d\n", i, f); 
    }
    return 0;
}

I truly don't understand why the Fibonacci Sequence, in this case, is a good place to start on recursion. It can be fiendishly complicated, and it doesn't seem practical because of how slow it can be. Your code is also incorrect for f0.

[wtetzner]

The Fibonacci sequence is defined as:

Code: Select all

fib(0) = 1
fib(1) = 1
fib(n) = (n - 2) + (n - 1) for n > 1

(Note that the above is not code, just the mathematical definition.)

What this says is that fib(0) returns 1, fib(1) returns 1, and for every integer n that is above 1, fib(n) returns the sum of the previous two values in the sequence.
So let's compute fib(2).

Code: Select all

Now, fib(n) = fib(n - 2) + fib(n - 1)
Then fib(2) = fib(2 - 2) + fib(2 - 1)
So   fib(2) = fib(0) + fib(1)
     fib(2) = 1 + 1, since fib(0) = 1 and fib(1) = 1

So when you write the function in code, you need to check if n = 0 or if n = 1. These are called the base cases or termination conditions. That's because they are not defined in terms of fib, so when you get a value n that is 0 or 1, it stops the recursion.
Everything else is defined in terms of fib.

Say you call fib with n = 4.
So fib(4) = fib(4 - 2) + fib(4 - 1)
Then fib(4) = fib(2) + fib(3)
Now fib(2) and fib(3) need to be computed in order to find fib(4).
So we compute fib(2):
fib(2) = fib(2 - 2) + fib(2 - 1)
fib(2) = fib(0) + fib(1)
So now we need to compute fib(0) and fib(1) to find fib(2)
But both fib(0) and fib(1) return 1. These are the base cases, since they don't call fib again.
So now we can finish computing fib(2).
fib(2) = fib(0) + fib(1)
fib(2) = 1 + 1
fib(2) = 2
Now we need fib(3) to finish computing fib(4), which we started computing above.
So fib(3) = fib(3 - 2) + fib(3 - 1)
fib(3) = fib(1) + fib(2)
Now we need to compute fib(1) and fib(2) to find fib(3).
fib(1) is a base case, and returns 1.
Computing fib(2) is the same as fib(2) above, which we discovered returns 2.
So fib(3) = fib(1) + fib(2)
fib(3) = 1 + 2
fib(3) = 3
Now we know both fib(2) and fib(3), so we can finish computing fib(4)
fib(4) = fib(2) + fib(3)
fib(4) = 2 + 3
fib(4) = 5

Hopefully I wasn't too unclear. The example was kind of long, but if you follow each step, you should be able to understand the process.

[wtetzner]

Actually I just though of a visual way to show how it works. Since fib calls two instances of itself, it creates a tree of function calls.

Code: Select all

                fib(4)
              /        \
        fib(2)    +      fib(3)
       /     \        /          \
  fib(0) + fib(1)   fib(1)   +   fib(2) 
    |       |         |          /     \  
    1       1         1       fib(0) + fib(1) 
                                 |       |  
                                 1       1

Hopefully that helps make things more clear.

[wearymemory]

Actually I just though of a visual way to show how it works. Since fib calls two instances of itself, it creates a tree of function calls.

Code: Select all

                fib(4)
              /        \
        fib(2)    +      fib(3)
       /     \        /          \
  fib(0) + fib(1)   fib(1)   +   fib(2) 
    |       |         |          /     \  
    1       1         1       fib(0) + fib(1) 
                                 |       |  
                                 1       1

Hopefully that helps make things more clear.

The fourth Fibonacci number is 3.

EDIT: FUCK! What's happening!?