1,105,447 Community Members

Recursion

Member Avatar
yun
Light Poster
42 posts since May 2009
Reputation Points: 0 [?]
Q&As Helped to Solve: 2 [?]
Skill Endorsements: 0 [?]
 
0
 

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);
	}
}
Member Avatar
siddhant3s
Practically a Posting Shark
816 posts since Oct 2007
Reputation Points: 1,429 [?]
Q&As Helped to Solve: 142 [?]
Skill Endorsements: 11 [?]
 
0
 

>>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)=""

Member Avatar
vali82
Light Poster
32 posts since Aug 2009
Reputation Points: 1 [?]
Q&As Helped to Solve: 4 [?]
Skill Endorsements: 0 [?]
 
0
 

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...

Member Avatar
siddhant3s
Practically a Posting Shark
816 posts since Oct 2007
Reputation Points: 1,429 [?]
Q&As Helped to Solve: 142 [?]
Skill Endorsements: 11 [?]
 
0
 

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

Member Avatar
Tom Gunn
Practically a Master Poster
681 posts since Jun 2009
Reputation Points: 1,164 [?]
Q&As Helped to Solve: 138 [?]
Skill Endorsements: 11 [?]
 
0
 

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

Member Avatar
yun
Light Poster
42 posts since May 2009
Reputation Points: 0 [?]
Q&As Helped to Solve: 2 [?]
Skill Endorsements: 0 [?]
 
0
 

it is my assignment :(

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article