recursion problem

[HG319]

We are going over recursion in my class and I do not quite understand it, I was wondering if someone can help me with this problem

[GRex2595]

First, what is c(n) supposed to do. Is it supposed to print all the variations? Or is it supposed to return the number of variations?

The process is relatively straightforward for this one. You'll want to start with low numbers, and move your way up. We'll start with 3 because it's shorter.

n=3=1+1+1=1+2=2+1=3
c(3)=c(n-1)+c((n-1)-1)+c(((n-1)-1)-1)=c(n-1)+c((n-1)-2)=c(n-2)+c((n-2)-1)=c(n-3)

It's a little difficult to see right away, but I'm sure you'll see it soon enough. As for part b, you'll only need a slight adjustment from part a.

[HG319]

so if i am writing a function where would the recursive part take place?

[GRex2595]

Typically, at the return, but it can take place throughout the function. The point of recursion is just to take one task and do it as a sum of similar tasks. Take the fibonacci recursive function, for example.

int fibonacci(int n)
{
     if(n < 1)
          return 0;
     if(n == 1)
          return 1;

     return fibonacci(n - 1) + fibonacci(n - 2);
}

This is something that should never be written, but it's a good example of how recursive functions are typically written.

[HG319]

int recurse_perm( int n)
 {
     if(n >= 1)
           n--;
          return (recurse_perm(n) + 1) + (recurse_perm(n));
    else if (n==1)
           return (recurse_perm(n) + 1+1); 
}

I am trying to figure out how to implement this design.
This is the problem where you count permutations.
I just want to map through it to make sure I understand. So if n=3. 3 >= 1, then n--;(2) it returns 2+1+2. So this would be wrong. right?

[GRex2595]

Okay, so you have the right idea so far. Your if else structure should be a little different. In recursion, you always have a base case (the case where the task can't get any smaller). That's usually in an if with a return of a constant (constant in this case, sometimes it can be a simple task, mergesort has a task at its base). Everything else is usually outside of the if statement.

So to correct it, you know that when n = 1, you know that the number of ways to get n is 1. If n != 1, then n should always be greater than 1, so you'll want to put if(n==1) at the top of the function with a return of 1. The rest of your function should compute the number of possible ways to get n when n is greater than 1.

Since you know that you can use numbers greater than 1 for each of your numbers (3 can be computed with 2+1), you'll want a loop to get numbers bigger than 1.

So far, so good. Just a little bit of work to fix it.

[HG319]

int recurse_perm( int n)
 {
     if(n == 1)
          return 1;
    else 
             while(n>1){
             n--;
          return (recurse_perm(n) - 1) + (recurse_perm(n));
        }
}

how does this look?

[GRex2595]

Looking really good, but there are a few logic errors.

It's not a big deal, but since you return in your if, you don't need an else. If you return, the rest of your function is ignored anyways. If you don't return, then you will always evaluate the rest of the function, so there's no reason to have the else.

Your loop is fine, but it returns early. It should accumulate the results from the recursion, and the function will return the accumulation at the end.

Let me write up the solution myself, and I'll help you out a little more specifically.

[HG319]

Thanks I would really appreciate that

int recurse_perm( int n)
 {
     if(n > 1){
             while(n>1){
             n--;
             //not sure what to do here
          return (recurse_perm(n) - 1) + (recurse_perm(n));
        }
      }
      else
           return 1;
}

[GRex2595]

Go back to your previous code and just delete the else, you don't need to restructure the whole function into an if else block.

int power(int base, int exponent)
{
	if (exponent == 0)
		return 1;
	else if (exponent == 1)
		return base;
	else
		return power(base * base, exponent / 2) * power(base, exponent % 2);
}

is exactly the same as

int power(int base, int exponent)
{
	if (exponent == 0)
		return 1;
	if (exponent == 1)
		return base;
	return power(base * base, exponent / 2) * power(base, exponent % 2);
}

This is because the return prevents any of the rest of the function from executing, so you won't need any elses in your function. The function will either evaluate the if, or it will evaluate the rest of the function.

[GRex2595]

I've built the function for part a.

You need a sum. I would set this to 1 at first, and we'll get to that if you can get the code.

You need a loop. It will loop from 1 to n-1. That's because the recursive call is going to sum everything from c(n - 1) to c(1).

You need a recursive call. Use my previous hints, and this should be relatively easy.

Also, for future reference, part a can be done in constant time. To make testing easier, the results should be 2^(n-1).

[GRex2595]

I've built the function for part b. Part a needs some modification, but it should be easy enough.

You need two variables for the parameters. One is for the number, and the other is the max. The max prevents numbers further down the recursive process from getting bigger than the earlier numbers (this cuts the permutations).

You need to initialize sum at 0. It may get the one back, but that's a special case.

Your loop will loop from 1 to max OR n-1. Again, if a number grows bigger than its predecessors, it will be a permutation.

[HG319]

int recurse_perm( int n)
 {
     int sum=1;
     if(n > 1){
             while(n>1){
             n--;
             sum+=1;
          return (recurse_perm(n) - 1) + (recurse_perm(n));
        }
      }
}

is this what you are talking about?

[GRex2595]

You're missing the base case (sort of).

int recurse_perm(int n)
{
	//base case
	if (num == 1)
		return 1;

	//no else
	int sum = 1;

	//loop from 1 to n-1
	//I suggest a for here

	return sum;
}

The question we have to ask is, "What is the base task?" The base task is counting all the ways to create n. How many ways can you create 1? 1. How many ways can you create 2? 1+1 and 2, which is 2. How many ways can we create 3? 1+1+1, 1+2, 2+1, and 3, which is 4.

Now the question is, "How do we get the recursive cases?" Take a look at the numbers I chose and how they are incremented. You start with all the low numbers, then you increase from the right. The right is going to be the lowest case. How can you keep the number in each recursive call so the numbers always add up?

[HG319]

int recurse_perm(int n)
{
	
	if (n == 1)
		return 1;


	int sum = 1;
    for(int i=n; i>1; i--){
            sum+=1;
            recurse_perm(n+1)+ recurse_perm(n); 
    }
	return sum;
}

I feel like I just keep getting confused

[GRex2595]

You're really close. That for loop iterates from n to 2, so you'll want to make it go from 1 to n-1.

The point of recursion is that you return the sum of your tasks. This means your sum won't add 1, but the recursive call.

your recursive call sort of goes the wrong way. If you have function c(n) that recursively computes the number of ways to calculate n with integers greater than 0, then c(3) should return the sum of c(2) and c(1). Why?

     [1]    [2]   [3]  [4]
3 = 1+1+1 = 1+2 = 2+1 = 3

Which will be implemented something like
c(1)=1
c(2)=1+c(1)
c(3)=1+c(2)+c(1)
. . .

Any better?

[GRex2595]

This problem is really bad for recursion imo. I wish this wasn't the recursive problem you were given.

[HG319]

int recurse_perm(int n)
{
	if (n == 1)
		return 1;
    
	int sum = 1;
    for(int i=n-1; i>n-1; i--){
            recurse_perm(n+1)+recurse_perm(n+1)+1;
            sum+=1; 
    }
	return sum;
}

[HG319]

int recurse_perm(int n)
{
	if (n == 1)
		return 1;
 
	int sum = 1;
    for(int i=n-1; i>n-1; i--){
            recurse_perm(n-1)+recurse_perm(n-2);
            sum+=1; 
          
    }
	return sum;
}

[HG319]

I am really struggling with this