Recursions Second Time around

This is a discussion on Recursions Second Time around within the C++ Programming forums, part of the General Programming Boards category; Ok, my second time around with this same problem.....now I understand the actually recursion, what it's doing and stuff but ...

  1. #1
    left crog... back when? incognito's Avatar
    Join Date
    Oct 2001
    Posts
    1,427

    Recursions Second Time around

    Ok, my second time around with this same problem.....now I understand the actually recursion, what it's doing and stuff but not the theory behind it.

    Take this for example

    Code:
    // Fibonacci series using recursion
    #include <iostream>
    
    int fib (int n);
    
    int main()
    {
    
    	int n, answer;
    	std::cout << "Enter number to find: ";
    	std::cin >> n;
    
    	std::cout << "\n\n";
    
    	answer = fib(n);
    
    	std::cout << answer << " is the " << n;
    		std::cout << "th Fibonacci number\n";
    	return 0;
    }
    
    int fib (int n)
    {
    	std::cout << "Processing fib(" << n << ")... ";
    
    	if (n < 3 )
    	{
    		std::cout << "Return 1!\n";
    		return (1);
    	}
    	else
    	{
    		std::cout << "Call fib(" << n-2 << ") ";
    			std::cout << "and fib(" << n-1 << ").\n";
    		return( fib(n-2) + fib(n-1));
    	}
    }
    From Sams Teach Yourself C++ in 21 days by Jesse Liberty

    Now that we got that over with.........it says that the nth number is equals to the sum of the two previous numbers or nth=n-1+n-2;

    right?


    Now the Theory behind this.....why must we dig down to the last two numbers 1,1 the first two numbers to add their return values in order to get the nth number, and not just do

    result=n-1+n-2 I know this is wrong for the most part Because if you do it with the number 6 it doesn't work since you get 5+4=9 and not 8 like it is........


    Thank you in advance, if you don't understand my question please tell me.
    There are some real morons in this world please do not become one of them, do not become a victim of moronitis. PROGRAMMING IS THE FUTURE...THE FUTURE IS NOW!!!!!!!!!

    "...The only real game I thank in the world is baseball..." --Babe Ruth

    "Life is beautiful"-Don Corleone right before he died.

    "The expert on anything was once a beginner" -Baseball poster I own.


    Left cprog on 1-3-2005. Don't know when I am coming back. Thanks to those who helped me over the years.

  2. #2
    Registered User
    Join Date
    Apr 2002
    Posts
    1,571
    It sounds like you answered your own question. Simply adding the number - 1 and -2 will simply not work as you disproved with your case.

    Consider the Fib. Seq.

    0,1,1,2,3,5,8,13...

    Its obvious to see starting at the beginning that is how the new numbers are generated ( (n - 1) + (n - 2) ). Maybe I don't understand what you are asking. Given an index of course it has to start at the beginning in order to work its way back.

    This probably didn't help

  3. #3
    left crog... back when? incognito's Avatar
    Join Date
    Oct 2001
    Posts
    1,427
    Well I understand Recursions, just don't understand the logic behind finding the Fib series with Recursions, recursions themselves I get it, not the logic used to solve this problem.

  4. #4
    Registered User
    Join Date
    Jan 2003
    Posts
    16
    Code:
    The Fib. Seq. is defined as...
     f(1)=1
     f(2)=1
     f(n)=f(n-1)+f(n-2)  
    
    so for example, the first 5 terms are...
    
    f(1) = 1  //by definition
    f(2) = 2  //by definition
    f(3) = f(n-1) + f(n-2) = f(3-1) + f(3-2) = f(2)+f(1) = 1 + 1 = 2
    f(4) = f(n-1) + f(n-2) = f(4-1) + f(4-2) = f(3)+f(2) = 2 + 1 = 3
    f(5) = f(n-1) + f(n-2) = f(5-1) + f(5-2) = f(4)+f(3) = 3 + 2 = 5
    
    so in order to find f(5) in other words...
      f(5) = f(4)+f(3)
    
    but, f(4) = f(3)+f(2) and f(3) = f(2)+f(1)
    so we get
      f(5) = f(3)+f(2) + f(2)+f(1)
    
    but, f(3) = f(2) + f(1)
    so we get
      f(5) = f(2)+f(1) + f(2) + f(2)+f(1)
    
    but by definition f(2) = 1 and f(1) = 1
    so we get
      f(5) =   1 +  1  + 1 + 1 +  1
           = 5
    The fib. seq. is defined using recursion. In order to find f(n)
    you have to call the function itself at least twice. Once for
    f(n-1) and once for f(n-2). Unless of course n<3.

    In the example above in order to find f(5) you have to find
    f(4),f(3),f(2), and f(1) first. What I tried to show in the example
    is that you can break any term in a fib. seq. down to terms of f(1)
    and f(2).

    Im not sure if this is what you meant by theory, but I hope it helps.
    James

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 11:43 AM
  2. Replies: 11
    Last Post: 03-29-2009, 01:27 PM
  3. Help with assignment!
    By RVDFan85 in forum C++ Programming
    Replies: 12
    Last Post: 12-03-2006, 12:46 AM
  4. time class
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 12-11-2001, 10:12 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21