Recursion

[Skynet]

Ok, So I am somewhat new to C++ and all and would like some help. I don't really know where to begin. I am currently working on recursion and I have to say that it is a very interesting topic but I don't know exactly how it works. I have this so far.

#include <iostream>
using namespace std;

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

void solveHanoi (int n, int A, int B, int C)
{
	if( n == 0 )
	{
	}
	else
	{
		solveHanoi(n-1, A, C, B);

		cout<<"Moving top disk from "<<A<<" to "<< C << endl;

		solveHanoi(n-1, B, A, C);


	}
}

int fib(int n)
{
	if (n==0)
		return 1;
	else if (n==1)
		return 1;
	return fib(n-1) + fib(n-2);
}

void drawLine(int n)
{
	for (int i=0; i<n; i++)
	{
		cout<<"*";
	}
	cout<<endl;
}

void stars(int n)
{
	if (n==0)
	{
	}

	if (n != 0)
	{
	drawLine(n);

	stars(n-1);

	drawLine(n);
	}
}

int numOnes(int n)
{
	if ( n == 0 )
	{
		return 0;
	}
	else
		return n%2 + numOnes(n/2);

}

int numFives(int n)
{
	if ( n == 0 )
	{
		return 0;
	}
	else
		return n%5 + numFives(n/10);
}


int main()
{
	solveHanoi(3, 1, 2, 3);

	cout<<fib(5)<< endl;

	stars(6);

	int n = 2;
	cout<<"The number of ones in "<<n<< " is "<<numOnes(n)<<endl;

	int x = 59;
	cout<<"The number of fives in "<<x<< " is "<<numFives(x)<<endl;
	
	return 0;
}

I have the stars code, solveHanoi, numOnes, and Fib working so far.

Stars, simply print stars on the screen.
numOnes, counts the number of ones in the binary code.
solveHanoi, well, solves Hanoi
Fib, I'm not sure how to explain it but it works. 1,1,2,3,5,8,13, etc...

For some reason I can't get numFives to work. It is simply suppose to count how many fives are in the numbers.

Another one that I need to implement, is one method that is suppose to accept a word and using recursion, tells me if it is a palindrome or not. After that, I need to implement something that gets a word and flips it. Example=elpmaxe.

Any help would be greatly appreciated.

[Duthomhas]

It seems you have the recursive idea down quite nicely.

The problem with numFives() is with your math.
To get the one's place, use the remainder of division by 10: ones = value % 10
To "shift down" by ten, just divide (as you do): value = value / 10

You are getting the remainder of division by 5 and adding that (whatever it may be) to the same for however many other places there are in the number.

You want, instead, to check to see if the one's place is a 5. If it is, add one to the result. Else add zero. (You can do this easily by simply converting the boolean value from your 'is it a five' test to an int, and add that to the recursive result.)

Hope this helps.

[Skynet]

I think one of my main problems is the fact that I need to get a better understanding of Recursive functions. I did this in class with my instructor and with his help I could get this down but I just can't seem to get it down without him hinting what to do. What exactly is Recursive I suppose is what I am trying to say.

[Kyon]

Recursion is a way of looping.
Loops can be performed in two ways, iteration and recursion.

Iteration is when you loop through a set of statements that execute until (or as long as, depending on the kind of loop you use) a condition is met, everything is done on the same "execution level".
Recursion is when you loop through a set of statements that calls for a new execution under certain conditions, this means that not everything is executed at the same "execution level".

Iteration is mostly found in normal language constructs like for, while and do-while.
Recursion is mostly found in function form, in which they call themselves.

[Skynet]

Recursion is when you loop through a set of statements that calls for a new execution under certain conditions, this means that not everything is executed at the same "execution level".

Iteration is mostly found in normal language constructs like for, while and do-while.
Recursion is mostly found in function form, in which they call themselves.

So basically, if I understand correctly, its calling itself over and over again with a new value each time?

As for my numFives, I am still having trouble with it Duoas. I don't really get what it is doing. I want it to say one for 59 but I only get random results like 11 or 19, or something else.

[Kyon]

Yes, that is correct. Analyzing one of your functions (int fib(int n)) we get this:

int fib(int n)
{
	if (n==0)
		return 1;
	else if (n==1)
		return 1;
	return fib(n-1) + fib(n-2);
}

If input is 3:

fib(3)
3 is not 0 or 1, this returns: fib(2)+fib(1).
  fib(2)
  2 is not 0 or 1, this returns: fib(1)+fib(0).
    fib(1)
    1 is 0 or 1, this returns: 1.
    Call to fib(1) ends.
      +
    fib(0)
    0 is 0 or 1, this returns: 1.
    Call to fib(0) ends.
  Call to fib(2) ends.
    +
  fib(1)
  1 is 0 or 1, this returns: 1.
  Call to fib(1) ends.
Call to fib(3) ends.

So the following pattern occurs:
fib(0) = 1
fib(1) = 1
fib(2) = 2
fib(3) = 3
fib(4) = 5
Etc.

Note that this is not the real Fibonacci sequence; it starts out with fib(0) = 0.

[Skynet]

int numFives(int n)
{
	if ( n == 0 )
	{
		return 0;
	}
	else
		return n%5 + numFives(n/10);
}

I think I see where you are going with that one so if that is the case then why does this not work. This is what I was thinking in my mind. I was thinking that if I pass it the value of 59 then it would divide it by 5 only to give me 4 and not add it to the counter and then divide by 10 to make it 5.9 which solves to 5 then repeat so that when I divide it by 5 there would be no remainder and it would add one to the counter. so overall it would say there is one 5 in the number but I just don't see where I am going wrong.

Sorry if it is obvious and I am just not seeing it.

[Skynet]

Also forgot to add, how would this work with the palindrome and reverse word recursion

[Duthomhas]

Consider the number 152357 as a list of digits: 1, 5, 2, 3, 5, 7.

You can check to see whether the end of the list is a five or not. In this case, it is not. Hence, we'll add zero to the result and recurse on what remains of the list: 1, 5, 2, 3, 5.

Now the end of the list is a five, so we'll add one to the result and recurse on what remains: 1, 5, 2, 3.

Continue for the remainder of the list, adding one if the end of the list is a five and zero if the end is not a five.

When there is no more list, we'll simply return zero -- stopping the recursion.

What essentially happens is your list:

    1 , 5 , 2 , 3 , 5 , 7

becomes a series of additions:

0 + 0 + 1 + 0 + 0 + 1 + 0

The recursion is seen in how we process the list: Another way of writing it is:

((((((( ) 1) 5) 2) 3) 5) 7)

which becomes:

(((((((0)+0)+1)+0)+0)+1)+0)

The problem you are having is figuring out how to convert "is the end of the list a five" into a one or a zero.

The "modulo" or "remainder" operator returns what is left over after a division. Remember in elementary school math you wrote "4 ÷ 5 = 0 R 4". In C++ that's 4 / 5 == 0 and 4 % 5 == 4.

You don't want to add the remainder of your division to the function. You would get:
0 + 1 + 0 + 2 + 3 + 0 + 7 --> 13, and that is definitely not the number of fives in the number.

Remember, to turn any number into a list, use n % 10 to see what the one's place is (the end of your list) and use n / 10 to get the remainder of the list. You know when you are out of list when the n is zero.

Hope this helps.

[Skynet]

I thought that was what I was doing in this solution

int numFives(int n)
{
	if ( n == 0 )
	{
		return 0;
	}
	else
		return n%10 + numFives(n/10);
}

Its not returning the correct number of fives but let me take a look at your explication again, I might be missing something.

[Duthomhas]

Re-read the stuff on math.

Your function only adds digits together.

  numFives( 123 ) --> 1 + 2 + 3 --> 6
  numFives( 271 ) --> 2 + 7 + 1 --> 10

Fix your function to only add one IFF ((n % 10) == 5), and add zero otherwise.

You can do this with an additional if statement or by casting your boolean test into an integer value.

[Skynet]

Ok, so I have tried everything but I can't get numFives to act right. Can anyone assist? I'm sorry if it is something I should know.

[Duthomhas]

You'll have to sleep on it. I can't give you a simpler answer without just giving you the answer.

Add 1 if the one's place is a five
Add 0 if the one's place is not a five

[edit] Fixed a typo. Late hour == dumb mistakes.

[Skynet]

Re-read the stuff on math.

Your function only adds digits together.

numFives( 123 ) --> 1 + 2 + 3 --> 6
numFives( 271 ) --> 2 + 7 + 1 --> 10

Fix your function to only add one IFF ((n % 10) == 5), and add zero otherwise.

You can do this with an additional if statement or by casting your boolean test into an integer value.

Let me try that.

[Skynet]

Ok, now I just can't figure this out. I just don't know what to do about it. This is what I tried now but it just doesn't work. numFives is my concern at this point.

#include <iostream>
using namespace std;

int counter = 0;

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

void solveHanoi (int n, int A, int B, int C)
{
	if( n == 0 )
	{
	}
	else
	{
		solveHanoi(n-1, A, C, B);

		cout<<"Moving top disk from "<<A<<" to "<< C << endl;

		solveHanoi(n-1, B, A, C);


	}
}

int fib(int n)
{
	if (n==0)
		return 1;
	else if (n==1)
		return 1;
	return fib(n-1) + fib(n-2);
}

void drawLine(int n)
{
	for (int i=0; i<n; i++)
	{
		cout<<"*";
	}
	cout<<endl;
}

void stars(int n)
{
	if (n==0)
	{
	}

	if (n != 0)
	{
	drawLine(n);

	stars(n-1);

	drawLine(n);
	}
}

int numOnes(int n)
{
	if ( n == 0 )
	{
		return 0;
	}
	else
		return n%2 + numOnes(n/2);

}

int numFives(int n)
{
	if ( n == 0 )
	{
		return 0;
	}
	else if ( n%10 == 5 )
	{
		counter++;
		return n%10 + numFives(n/10);
	}
	else 
		numFives(n/10);
}


int main()
{
	solveHanoi(3, 1, 2, 3);

	cout<<fib(5)<< endl;

	stars(6);

	int n = 2;
	cout<<"The number of ones in "<<n<< " is "<<numOnes(n)<<endl;

	int x = 59;
	cout<<"The number of fives in "<<x<< " is "<<counter<<endl;
	
	return 0;
}

[Duthomhas]

You are ever so very close.

What the hades is counter? Your recursion should be one of:

  return 1 + numFives(n/10);

  return     numFives(n/10);

The hardest part about computer science is wrapping your head around some concepts. Once you "get it" you are set.

[Skynet]

#include <iostream>
using namespace std;

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

void solveHanoi (int n, int A, int B, int C)
{
	if( n == 0 )
	{
	}
	else
	{
		solveHanoi(n-1, A, C, B);

		cout<<"Moving top disk from "<<A<<" to "<< C << endl;

		solveHanoi(n-1, B, A, C);


	}
}

int fib(int n)
{
	if (n==0)
		return 1;
	else if (n==1)
		return 1;
	return fib(n-1) + fib(n-2);
}

void drawLine(int n)
{
	for (int i=0; i<n; i++)
	{
		cout<<"*";
	}
	cout<<endl;
}

void stars(int n)
{
	if (n==0)
	{
	}

	if (n != 0)
	{
	drawLine(n);

	stars(n-1);

	drawLine(n);
	}
}

int numOnes(int n)
{
	if ( n == 0 )
	{
		return 0;
	}
	else
		return n%2 + numOnes(n/2);

}

int numFives(int n)
{
	if ( n == 0 )
	{
		return 0;
	}
	else if ( n%10 == 5 )
	{
		return 1 + numFives(n%10);
	}
	else 
		return 0 + numFives(n/10);
}


int main()
{
	solveHanoi(3, 1, 2, 3);

	cout<<fib(5)<< endl;

	stars(6);

	int n = 2;
	cout<<"The number of ones in "<<n<< " is "<<numOnes(n)<<endl;

	int x = 59;
	cout<<"The number of fives in "<<x<< " is "<<numFives(x)<<endl;
	
	return 0;
}

I thought this would work but I guess not.

[Duthomhas]

Why are you calling numFives() with an argument of n%10 ?

[Skynet]

Why are you calling numFives() with an argument of n%10 ?

Oh.......Didn't see that coming. I'll be damned, it works! Thank you all for helping. I'm sorry I didn't pick this up faster. Here is the completed code.

#include <iostream>
using namespace std;

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

void solveHanoi (int n, int A, int B, int C)
{
	if( n == 0 )
	{
	}
	else
	{
		solveHanoi(n-1, A, C, B);

		cout<<"Moving top disk from "<<A<<" to "<< C << endl;

		solveHanoi(n-1, B, A, C);


	}
}

int fib(int n)
{
	if (n==0)
		return 1;
	else if (n==1)
		return 1;
	return fib(n-1) + fib(n-2);
}

void drawLine(int n)
{
	for (int i=0; i<n; i++)
	{
		cout<<"*";
	}
	cout<<endl;
}

void stars(int n)
{
	if (n==0)
	{
	}

	if (n != 0)
	{
	drawLine(n);

	stars(n-1);

	drawLine(n);
	}
}

int numOnes(int n)
{
	if ( n == 0 )
	{
		return 0;
	}
	else
		return n%2 + numOnes(n/2);

}

int numFives(int n)
{
	if ( n == 0 )
	{
		return 0;
	}
	else if ( n%10 == 5 )
	{
		return 1 + numFives(n/10);
	}
	else 
		return 0 + numFives(n/10);
}


int main()
{
	solveHanoi(3, 1, 2, 3);

	cout<<fib(5)<< endl;

	stars(6);

	int n = 2;
	cout<<"The number of ones in "<<n<< " is "<<numOnes(n)<<endl;

	int x = 55;
	cout<<"The number of fives in "<<x<< " is "<<numFives(x)<<endl;
	
	return 0;
}

[Duthomhas]

:-)