Recursion difficulties, very lost

**LearnOnTheFly** · 03-27-2012

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

**TheBigH** · 03-27-2012

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.

**LearnOnTheFly** · 03-27-2012

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?

**TheBigH** · 03-27-2012

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.

**LearnOnTheFly** · 03-27-2012

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) ;
}

**TheBigH** · 03-27-2012

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?

**LearnOnTheFly** · 03-27-2012

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?

**oogabooga** · 03-27-2012

You don't need the result variable (in factorial). Just return the result.

**LearnOnTheFly** · 03-27-2012

Ok thank you, my formula r*n(n-1) returns an error saying n is not a function

**laserlight** · 03-27-2012

It is invalid syntax for what you want to do. You should use * for multiplication.

**LearnOnTheFly** · 03-27-2012

Ah its always something so small, thank you for your laser

Thread: Recursion difficulties, very lost

Thread Tools

Search Thread

Display

Recursion difficulties, very lost

Similar Threads

finding difficulties

difficulties with UNIX

difficulties w/connection