C++ Recursion Help

[Calibur]

Hi, Im new to programming. I am taking a class at a local college and I don't really understand how to create recursion. I have a homework problem that requires me to input an integer between 1 and 32767 and print is as a series of digits each digit is separated by 2 spaces. i.e 4762 would be 4 7 6 2. Could anybody help me out with the recursion. I have a forumla to calculate the number of the digits and it is:

double logint;//
cout << "Please input an integer between 1 and 32767: "; // Input
cin >> number;

logint = log10(number); // The floor of the log base 10 + 1 is equal to the number of digits in the integer

numberdig = floor(logint+1);

where numberdig is the number of digits in the number.

Could someone help?
Edit/Delete Message

 

[scott123]

sorry if this doesnt help, it would be much easier to do with strings.

#include<iostream>
#include<string>
//i forget if you have to include anything for atoi function
using namespace std;

a non recursive example:

int main()
{
string num;
cin >> num;
for( int i =0; i < num.size(); i++){
cout << num << " ";
}
return 0;
}


a recursive example

void print(string num)
{
if( num.size() != 0){
cout << num[0] << " ";
string num2;
num2 = num.substr(1,num.size()-1);
print(num2);
}
int main()
{
string num;
cin >> num;
print(num);
return 0;
}


edit: if you want to change the string to an int to test if it in the right range you can just do this:

string x;
int y = atoi( x.c_str() );

 

[jpmkm]

The basic idea with recursion is that you have a function that keeps calling itself recursively until it is done doing what it needs to do. In this case, you would have a function that prints the first digit of a number(and then a space or whatever else you need), and then calls itself with the remaining digits as a parameter. Using recursion I don't think you really need to know the number of digits; the function would just keep calling itself until the input was exhausted. Extracting the first digit is another story altogether, but since you were just asking about recursion I will assume you know how to do that.

edit: scott: yeah I was kinda thinking this would be much simpler using a string rather than an int.

 

[Cardboard Hammer]

Actually, with recursion, it'd be easier to make the recursive call before printing. If number > 0, pass the number/10 into the recursive call, then print number%10 and the spaces.

 

[mikeblas]

It's pretty silly to solve this with recursion, but if that's the assignment, I guess that's the assignment. For recursion, what CH says is right on. The trick is to remember to print the digit after recurring for the rest of the digits.

 

[ameoba]

It's pretty silly to solve this with recursion, but if that's the assignment, I guess that's the assignment. For recursion, what CH says is right on. The trick is to remember to print the digit after recurring for the rest of the digits.

Most of the exercises you do when trying to figure out something like recursion are going to be silly anyways and this is one of the standard silly recursion exercises. There's really very few simple things you can do with recursion that are both visbily write or wrong and don't require you to learn how something complex works.

 

[Whatsisname]

i've always considered the greatest common denominator (i think) problem to be the classic recursion example because i have seen it everywhere.

 

[jpmkm]

The two big recursion examples I can think of are factorial and fibonacci sequence(though most standard recursive algorithms for that are inefficient as hell).

 

[mikeblas]

Right; factorial, fibbonacci, and factoring problems are good and meaningful ways to learn and apply recursion. The thing is, it's probably more important to know when to apply recursion as a technique than it is to know only how to go and implement it.

 

[scott123]

part of a homework problem in comp sci 2 was to do gcd with recursion. we also had to do the "N attacking queens" thing ( you can google it) which i couldnt do. i remember part of one of the tests was to write a recursive and non recusrive fibbonacci function.

 

[HorsePunchKid]

The thing is, it's probably more important to know when to apply recursion as a technique than it is to know only how to go and implement it.

And certainly if you go on to study actual computer science -- the branch of mathematics, as opposed to the codemonkey vocation -- you'll find that recursion is a fundamentally important and extremely powerful theoretical tool (the Master Theorem and all that rot).

 

[piller1999]

...you'll find that recursion is a fundamentally important and extremely powerful theoretical tool (the Master Theorem and all that rot).

That theorem really helped me out in one of my CS classes.

 

[ameoba]

As an interesting aside - GCD and Factorial commute - that is to say that

fact(gcd(x,y)) == gcd(fact(x),fact)

the proof is pretty tedious.

 

[n64man120]

Speaking of recursion, I think it's one of the most PITA thigns i've had to learn and do

It's not that hard, but whyyyyy

 

[mikeblas]

Speaking of recursion, I think it's one of the most PITA thigns i've had to learn and do

It's not that hard, but whyyyyy

Whyyyyy what? Whyyyyy learn it? Whyyyyy is it important? Whyyyyy is it hard?

 

[Whatsisname]

try collapsing a binary tree using iteration. It's a goddamn pain in the butt. With recursion it is easy as cake though. However you have to watch out if your tree is large, otherwise you'll have a stack overflow in no time.

Speaking of recursion, I think it's one of the most PITA thigns i've had to learn and do

It's not that hard, but whyyyyy

 

[Xipher]

Yea, their are just some problems that are extreamly difficult without recursion, and others that just end up alot easier (even if they were pretty easy before).

 

[scott123]

try collapsing a binary tree using iteration. It's a goddamn pain in the butt. With recursion it is easy as cake though. However you have to watch out if your tree is large, otherwise you'll have a stack overflow in no time.

after 1 year in college of taking c++ classes, this is the only thing i can remember where it was pretty much necessary.

 

[jpmkm]

Recursion is also used heavily in functional programming.

 

[n64man120]

Well I guess it's because my AP Comp Sci class was taught at a 5th grade level, and I got a 102 average in the class after not handing in any HW assignments

 

[BillLeeLee]

Sounds like a winner of a class.

Recursion is elegant and simple, the main thing I have used it for is for making moves in zero-sum games of perfect information. However, what I do hate are textbooks' descriptions of the algorithms involved, like Alpha-Beta Pruning and Minimax.

 

[mrgstiffler]

I'm taking a programming class right now in Lisp. The professor doesn't allow us to use any loop structure or global variables. It's extremely difficult at first, but then once you get your head around it, you really start thinking a different way...