Recursion difficulties, very lost

This is a discussion on Recursion difficulties, very lost within the C Programming forums, part of the General Programming Boards category; I'm working on an assignment that wants me to recursively determine the value of the nth term of a geometric ...

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    98

    Recursion difficulties, very lost

    I'm working on an assignment that wants me to recursively determine the value of the nth term of a geometric sequence defined by the terms

    a, ar, ar^2(squared), ar^3(cubed),.....ar^n-1

    It also note that the argument should be the first term a, the common ratio r, and the value of n

    The section in the book covers recursion very briefly and I'm struggling to figure out how to start this assignment. Any pointers or exampes to get me going would greatly be appreciated

    The code is not the assignment but the only skeleton the book gives of recursion

    Code:
    #include
    <stdio.h>
    #pragma
    warning (disable : 4996)
    int
     main ()
    {
    	
    int n, result;
    	
    int factorial (int);
    	printf(
    "Enter a number: ");
    	scanf(
    "%d", &n);
    	result = factorial(n);
    	printf(
    "\nThe factorial of %d is %d\n", n, result);
    	
    return 0;
    }
    int
     factorial (int result)
    {
    	result
    

  2. #2
    Registered User TheBigH's Avatar
    Join Date
    May 2010
    Location
    Melbourne, Australia
    Posts
    426
    Well, the first thing to recognize is that each term is r times the previous one. That is, term(m) = r*term(m-1). This is a recursive definition because each term is defined using the previous ones.

    Things like this can be elegantly coded in C because functions can call themselves. All you need to know is how to construct the next term from previous ones, and how to deal with the simplest case which tells you where to stop the recursion.

    I'll give you an example of the factorial function done recursively so you can see how it works

    Code:
    int factorial( int n ) {
       if( n==1 ) 
          return 1;       /* the factorial of 1 is 1. This requires no multiplications to calculate and so we can just stop here */
    
       return n*factorial( n-1 );   /* this is the recursive step. It's based on the fact that n! = n*(n-1)!
    }
    Let's walk through and see what this does, starting with n=6. For the first call to the factorial, n does not equal 1 so we move on to the recursive bit. It therefore returns 6 times factorial(5). This second call to factorial returns 5*factorial(4) and so on
    Code:
    factorial(6) = 6*factorial(5)
                 = 6*5*factorial(4)
                 = 6*5*4*factorial(3)
                 = 6*5*4*3*factorial(2)
                 = 6*5*4*3*2*factorial(1)
                 = 6*5*4*3*2*1
    In the last step we don't recurse anymore because we've reached the base case. If we did not include the base case we'd go on calculating factorial(0), factorial(-1) and so on forever.

    In your assignment can you define the recursive step and the base case? Once you've got these you'll easily be able to implement it as code.
    Code:
    while(!asleep) {
       sheep++;
    }

  3. #3
    Registered User
    Join Date
    Mar 2012
    Posts
    98
    So do I set a value for the common ratio? Also, on the part of code you wrote that starts with factorial(6) is that part of the code that needs to be written or is it an example of what is happening?

  4. #4
    Registered User TheBigH's Avatar
    Join Date
    May 2010
    Location
    Melbourne, Australia
    Posts
    426
    That second bit is just an illustration of what is going on, not actual code.

    The common ratio is "r", right? So you should pass that into the recursive function as one of the arguments.
    Code:
    while(!asleep) {
       sheep++;
    }

  5. #5
    Registered User
    Join Date
    Mar 2012
    Posts
    98
    I understand the factorial but I am struggling to implement the idea into my code. I think I'm heading in the wrong direction quickly

    Code:
    int nth term(int, int)
    int main ()
    {
     int n, result, r;
     printf("Enter a number: ");
     scanf("%d", &n);
     result = r*n(n-1);
     printf("\nThe nth term of %d is %d\n", n, result);
     return 0;
    }
    int factorial (int result, int n)
    {
     int r=2;
     result = r*n(n-1) ;
    }

  6. #6
    Registered User TheBigH's Avatar
    Join Date
    May 2010
    Location
    Melbourne, Australia
    Posts
    426
    Firstly, you can't have a function name made consisting of two words. Call it nth_term instead.

    Next, explain in words how to compute the nth member of the sequence in terms of the (n-1)th.
    Then explain in words what the base case is; where do you stop the recursive process?
    Code:
    while(!asleep) {
       sheep++;
    }

  7. #7
    Registered User
    Join Date
    Mar 2012
    Posts
    98
    The value of the nth term would be term*ratio^(term-1)
    I'm still having trouble understanding what the base case would be. I understand how it works when using a factorial but my program does not need the use of a factorial right?

  8. #8
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    You don't need the result variable (in factorial). Just return the result.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  9. #9
    Registered User
    Join Date
    Mar 2012
    Posts
    98
    Ok thank you, my formula r*n(n-1) returns an error saying n is not a function

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,990
    It is invalid syntax for what you want to do. You should use * for multiplication.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Mar 2012
    Posts
    98
    Ah its always something so small, thank you for your laser

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. finding difficulties
    By luke luvevou in forum C++ Programming
    Replies: 6
    Last Post: 05-18-2009, 03:00 AM
  2. difficulties with UNIX
    By tytelizgal in forum Linux Programming
    Replies: 1
    Last Post: 10-18-2008, 04:29 AM
  3. difficulties w/connection
    By dP munky in forum Networking/Device Communication
    Replies: 5
    Last Post: 02-09-2005, 02:48 PM

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