Recursion

[yun]

Hey Programmers,
Is there any better way to write the below recusive functions, plz help me so i can improve my programming...

1-
Write a recursive function that takes a nonnegitive integer and returns the sum of its digits,

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

}

2-
Write a recursive function DigitalRoot(int n) that returns the digital root of its arguments.

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

}

int DigitRoot(int n){
	if((n/10) < 1){
		return n;		
	}else{
		return DigitRoot(DigitSum(n));
	}
}

3- Reverse string

string Reverse(string str){
	if(str.length()==1){
		return str;
	}else{
		return str[str.length()-1] + Reverse(str.substr(0,str.length()-1));
	}
}

4-
write a recursive function to convert integer into string.

string IntToString(int n){
	if(n==0){
		return "";
	}else{
		return IntToString(n/10) + (char)((n%10)+48);
	}
}

[siddhant3s]

>>write a recursive function to convert integer into string.
Your function will work good for all positive integer but would fail when N=0.
IntToString(0)=""

[vali82]

Hi,

Not sure if recursive is your assignment or not, bu if it's not ... you could do a far better job on some of the functions without it.

Recursive functions should be used as sparingly as possible as they are extremely slow...

[siddhant3s]

>Recursive functions should be used as sparingly as possible as they
>are extremely slow
Yes. But looking at the other side of the coin, recursive function tend to be easy to model than iterative algorithms.
For say, fibonacci sequence, you can immediately model the function by applying the direct (recursive) definition while the iterative version will surely catch your brain for at least 2-3 minutes (if you are a beginner)

[Tom Gunn]

Recursive functions should be used as sparingly as possible as they are extremely slow...

Potentially slow. Compilers do not have to do a function call mechanism with the usual stack frame setup that has the lion's share of overhead. For some tail recursive functions, compilers can easily optimize them into iteration and there is no speed difference at all. The overhead of recursion is not usually enough to be a deciding factor, but the risk of stack overflow should always be considered.

Recursion should be used when it makes sense to do so. But when it makes sense depends on things like how much complexity is reduced by switching from iteration to recursion, how much risk of stack overflow there is, whether you need to break out of the recursive loop, and speed/memory usage.

For say, fibonacci sequence, you can immediately model the function by applying the direct (recursive) definition while the iterative version will surely catch your brain for at least 2-3 minutes (if you are a beginner)

Then those 2-3 minutes are time well spent. :D Unless previous results are cached, the recursive algorithm for calculating the fibonacci sequence is very inefficient. If you are a beginner, you probably will not think about this, and the 2-3 minutes of catching your brain will save you from using a really bad algorithm. ;)

[yun]

it is my assignment :(