Thread: Help about recursion

  1. #1
    Registered User
    Join Date
    Dec 2010
    Posts
    20

    Help about recursion

    0,2,8,26,80,242,728,2186,6560,19682....how can i write these series with recursion?
    if we start k=0 and then return the function 3k+2 we can get that but I don't know how to turn this into code,can you help me about that?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    All recursion can be broken up into two pieces:
    A - the "base case" when you've reached the "bottom" (or the "beginning")

    B - every other case, where you call the function with a smaller value, then manipulate that value as necessary.

  3. #3
    Registered User
    Join Date
    Dec 2010
    Posts
    20
    Could you be more specific?

  4. #4
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Figen View Post
    0,2,8,26,80,242,728,2186,6560,19682....how can i write these series with recursion?
    if we start k=0 and then return the function 3k+2 we can get that but I don't know how to turn this into code,can you help me about that?
    First of all, the mods here take a rather dim view of people using us to do their homework.

    You really need to make your best effort on this, on your own, and if you run into problems post your code (in code tags please) and we'll see what we can do...

    FWIW... you don't actually need recursion to solve this problem...

  5. #5
    Registered User
    Join Date
    May 2010
    Location
    Naypyidaw
    Posts
    1,314
    Mathematically
    Code:
    f(k) = 3 * f(k-1) + 2;  k > 0
    f(0) = 0;
    Edit: Just apply what tabstop said.

  6. #6
    Registered User
    Join Date
    Jul 2007
    Posts
    131
    Quote Originally Posted by CommonTater View Post
    FWIW... you don't actually need recursion to solve this problem...
    I think the hook here is to do it with recursion. I think he would've come up with some other way to implement it if his job was just to implement that series.

  7. #7
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by fronty View Post
    I think the hook here is to do it with recursion. I think he would've come up with some other way to implement it if his job was just to implement that series.
    I figured it was an assignment for some course or another.

    It's just that recursion is, to say the least, not the safest way of doing things where you have another choice on hand.

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Figen View Post
    Could you be more specific?
    Nope, that's pretty much as fundamental as it gets. What do you do when n=0, and what do you do when n doesn't equal 0.

  9. #9
    Registered User
    Join Date
    Dec 2010
    Posts
    20
    Okey then I will give a shot that here and please help me to improve it
    Code:
    main()
    
    {
    
      int i,k=0;
    
      printf("%d,",k);
     
      recursion();
      
      printf("%d,",k);
    
    }
    
    recursion()
    
    {
    
     for(i=0;i<13;i++) {
    
      k=3k+2;
    
      return k;
    
    }
    Now how about some assitment now?

  10. #10
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Recursion is when a function calls itself, meaning you enter function foo and foo also calls foo, unless the base case is true, which is the bottom. At the bottom, now you unwind all the way to the top, resolving all the statements that depended on previous calls of foo.

  11. #11
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    That's not recursion. Recursion is when a function calls itself. Your function is iterative and only calculates the value of the summation for k equal to 13. You don't calculate for k = 1, 2, ... 12. An example of recrusion would look like:
    Code:
    void factorial(int x)
    {
        if (x == 0)  // base case, i.e. stop the recursion
            return 1;
        else
            return x * factorial(x - 1);  // recurse by calling foo with some other value
    }
    Put that together with tabstop's and Baying Naung's posts, and you should be able to come up with a solution.

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is the basic layout of a recursive function:

    Code:
    #include <stdio.h>
    
    void recurse(int n);
    
    int main() {
      int n; 
      
      n=0;
      recurse(n);
    
      printf("\n\n\t\t\t     press enter when ready");
    
      (void) getchar(); 
      return 0;
    }
    void recurse(int n) {
      if (n>10)      //the base case, 
        return;
      printf("n = %d\n", n);
      recurse(n+1); //recursive calls
    
    //you don't need to change your variables inside the parameter parenthesis ( )
    //having n+= 1; and then recurse(n) is equivalent.
    }

  13. #13
    Registered User
    Join Date
    Dec 2010
    Posts
    20
    Code:
    main()
    
    {
    
      int i,k=0;
    
      printf("%d,",k);
      for(i=0;i<13;i++){
      recursion(k);
      printf("%d,",k);
      }
    
    }
    
    recursion(k)
    
    {
    
    
      k=3k+2;
    
      return recursion(k);
    
    }
    How about that now?

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    That's ... pretty horrific. Your first step, which you seem to want to skip but can't, is to write down, in words, what should happen.

    In other words, if I give you 6, you're supposed to give me 728 (if I'm reading your top post correctly and not off-by-one). How do you, yourself, get from 6 to 728?

  15. #15
    Registered User
    Join Date
    Dec 2010
    Posts
    20
    you are not giving anything here...there is no interaction with user.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  3. Recursion
    By Lionmane in forum C Programming
    Replies: 11
    Last Post: 06-04-2005, 12:00 AM
  4. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  5. stack and recursion help needed!
    By LouB in forum C++ Programming
    Replies: 3
    Last Post: 07-01-2002, 02:19 PM