Jump to content
  • Advertisement
Sign in to follow this  
S_S

Recursive Function

This topic is 5132 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

/*Write the routines with the following declarations void permute( const string & str); void permute( const string & str, int low, int high); The first routine is a driver that calls the second and prints all the permutations of the characters in string str. If str is "abc", then the strings that are output are abc, acb, bac, bca, cab, and cba. Use recursion for the second routine*/ any solution?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by arm
I smell me a homework assignment.

no this is a general problem.
i only want to learn how can it can be done?
can you help me please? :)

Share this post


Link to post
Share on other sites
Every recursive function has a base case, a case where the function would simply return. Then there is the inductive case, where it would call itself but slightly changed the parameter that it drops down to the base case. If you are writing a fibonacci recursive function, we know that fibonacci formula is fn = fn-1 + fn-2. The base case of fibonacci sequence is when n = 0 and n = 1. If n is 10, it calls itself for 9 and 8. The 9 will call for 8 and 7, and the 8 will call for 7 and 6, and so on until it reaches 0 and 1.

You just need to figure how permutation works, break it down to base and inductive case, then write the recursion.

Share this post


Link to post
Share on other sites
Quote:
Original post by alnite
Every recursive function has a base case, a case where the function would simply return. Then there is the inductive case, where it would call itself but slightly changed the parameter that it drops down to the base case. If you are writing a fibonacci recursive function, we know that fibonacci formula is fn = fn-1 + fn-2. The base case of fibonacci sequence is when n = 0 and n = 1. If n is 10, it calls itself for 9 and 8. The 9 will call for 8 and 7, and the 8 will call for 7 and 6, and so on until it reaches 0 and 1.

You just need to figure how permutation works, break it down to base and inductive case, then write the recursion.

i have problems about writing this functions base and inductive case so i couldn't write the recursion.

i searched at internet and no answer for my question.

Share this post


Link to post
Share on other sites
Quote:
Original post by Jingo
std::next_permutation
std::prev_permutation
Yeah, just go into the code for the STL header algorithm and you'll find how these are implemented. They're actually quite short.

Share this post


Link to post
Share on other sites
low and high are supposed to indicate endpoints of a substring to permute.

What is the shortest possible length for a substring? What are the permutations of such a string?

Given a way to permute n characters, how can you permute n+1 characters? Hint: What are the possibilities for the first character of a permutation? Given the first character, what are the possibilities for the others?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!