[SOLVED]

Whether you're a newbie or an experienced programmer, any questions, help, or just talk of any language will be welcomed here.

Moderator: Coders of Rage

User avatar
short
ES Beta Backer
ES Beta Backer
Posts: 548
Joined: Thu Apr 30, 2009 2:22 am
Current Project: c++, c
Favorite Gaming Platforms: SNES, PS2, SNES, SNES, PC NES
Programming Language of Choice: c, c++
Location: Oregon, US

Re: Visual c++ 2008 version

Post by 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.
My github repository contains the project I am currently working on,
link: https://github.com/bjadamson
User avatar
avansc
Respected Programmer
Respected Programmer
Posts: 1708
Joined: Sun Nov 02, 2008 6:29 pm

Re: Visual c++ 2008 version

Post by 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.
Some person, "I have a black belt in karate"
Dad, "Yea well I have a fan belt in street fighting"
User avatar
avansc
Respected Programmer
Respected Programmer
Posts: 1708
Joined: Sun Nov 02, 2008 6:29 pm

Re: Visual c++ 2008 version

Post by 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
Some person, "I have a black belt in karate"
Dad, "Yea well I have a fan belt in street fighting"
User avatar
jtst1
Chaos Rift Cool Newbie
Chaos Rift Cool Newbie
Posts: 80
Joined: Tue Sep 30, 2008 4:32 pm
Location: Atlanta Georgia

Re: Visual c++ 2008 version

Post by jtst1 »

avansc wrote: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.
When One learns to Love, One must bear the risk of Hatred.
User avatar
avansc
Respected Programmer
Respected Programmer
Posts: 1708
Joined: Sun Nov 02, 2008 6:29 pm

Re: Visual c++ 2008 version

Post by 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.
Some person, "I have a black belt in karate"
Dad, "Yea well I have a fan belt in street fighting"
User avatar
jtst1
Chaos Rift Cool Newbie
Chaos Rift Cool Newbie
Posts: 80
Joined: Tue Sep 30, 2008 4:32 pm
Location: Atlanta Georgia

Re: Visual c++ 2008 version

Post by jtst1 »

avansc wrote: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
When One learns to Love, One must bear the risk of Hatred.
User avatar
dandymcgee
ES Beta Backer
ES Beta Backer
Posts: 4709
Joined: Tue Apr 29, 2008 3:24 pm
Current Project: https://github.com/dbechrd/RicoTech
Favorite Gaming Platforms: NES, Sega Genesis, PS2, PC
Programming Language of Choice: C
Location: San Francisco
Contact:

Re: Visual c++ 2008 version

Post by dandymcgee »

jtst1 wrote: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.
jtst1 wrote: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. ;)
jtst1 wrote: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.
Falco Girgis wrote:It is imperative that I can broadcast my narcissistic commit strings to the Twitter! Tweet Tweet, bitches! :twisted:
User avatar
jtst1
Chaos Rift Cool Newbie
Chaos Rift Cool Newbie
Posts: 80
Joined: Tue Sep 30, 2008 4:32 pm
Location: Atlanta Georgia

Re: Visual c++ 2008 version

Post by 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.
When One learns to Love, One must bear the risk of Hatred.
User avatar
Falco Girgis
Elysian Shadows Team
Elysian Shadows Team
Posts: 10294
Joined: Thu May 20, 2004 2:04 pm
Current Project: Elysian Shadows
Favorite Gaming Platforms: Dreamcast, SNES, NES
Programming Language of Choice: C/++
Location: Studio Vorbis, AL
Contact:

Re: Orginal solved. Anyone know Recursion?

Post by 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.
User avatar
jtst1
Chaos Rift Cool Newbie
Chaos Rift Cool Newbie
Posts: 80
Joined: Tue Sep 30, 2008 4:32 pm
Location: Atlanta Georgia

Re: Orginal solved. Anyone know Recursion?

Post by 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?
When One learns to Love, One must bear the risk of Hatred.
User avatar
Falco Girgis
Elysian Shadows Team
Elysian Shadows Team
Posts: 10294
Joined: Thu May 20, 2004 2:04 pm
Current Project: Elysian Shadows
Favorite Gaming Platforms: Dreamcast, SNES, NES
Programming Language of Choice: C/++
Location: Studio Vorbis, AL
Contact:

Re: Orginal solved. Anyone know Recursion?

Post by Falco Girgis »

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

...working our asses off.
wearymemory
Chaos Rift Junior
Chaos Rift Junior
Posts: 209
Joined: Thu Feb 12, 2009 8:46 pm

Re: Orginal solved. Anyone know Recursion?

Post by 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.
Last edited by wearymemory on Thu Jul 30, 2009 1:54 am, edited 6 times in total.
User avatar
wtetzner
Chaos Rift Regular
Chaos Rift Regular
Posts: 159
Joined: Wed Feb 18, 2009 6:43 pm
Current Project: waterbear, GBA game + editor
Favorite Gaming Platforms: Game Boy Advance
Programming Language of Choice: OCaml
Location: TX
Contact:

Re: Orginal solved. Anyone know Recursion?

Post by 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.
The novice realizes that the difference between code and data is trivial. The expert realizes that all code is data. And the true master realizes that all data is code.
User avatar
wtetzner
Chaos Rift Regular
Chaos Rift Regular
Posts: 159
Joined: Wed Feb 18, 2009 6:43 pm
Current Project: waterbear, GBA game + editor
Favorite Gaming Platforms: Game Boy Advance
Programming Language of Choice: OCaml
Location: TX
Contact:

Re: Orginal solved. Anyone know Recursion?

Post by 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.
The novice realizes that the difference between code and data is trivial. The expert realizes that all code is data. And the true master realizes that all data is code.
wearymemory
Chaos Rift Junior
Chaos Rift Junior
Posts: 209
Joined: Thu Feb 12, 2009 8:46 pm

Re: Orginal solved. Anyone know Recursion?

Post by wearymemory »

wtetzner wrote: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!?
Last edited by wearymemory on Thu Jul 30, 2009 2:05 am, edited 1 time in total.
Post Reply