improve speed of recursive function

Question

0.00/5 (No votes)

See more:

Layout of recursive function that I am using is below

C++

fun1()
{
for()
  {
    for()
     {
        if (this)
           {
            .....
           fun2()
           }
        else
           {
            ....
           fun2()
           }
     } 
  }
}


fun2()
{
 .........
........
   fun1();

}

It works fine as I want. The only constraint is speed. Can multithreading solve the problem ? or any another solution.. or u have no solution.. thanx in advance

Posted 31-Jul-10 2:20am

himani_jha

Add a Solution

4 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Toli Cuturicu · Answer 1 · 2010-07-31T02:28:00

Solution 1

Wow! Two nested for cycles AND recursion! This must be really slow.
What in the earth are you doing? Calculating matrix determinants?
Of course there are way better algorithms available and free. Just google for them (you can also find some here on CodeProject).

Posted 31-Jul-10 2:28am

Toli Cuturicu

Comments

himani_jha 31-Jul-10 9:17am

Tell the keyword to search the solution. suggest answer plz??

Christian Graus 3-Aug-10 19:52pm

No-one can suggest an answer based on what you posted, because we can't see what your loops are, to suggest how to optimise them. Multithreading is unlikely to help, unless your code is through multithreading able to access many cores. Multi threading makes your code more complex and harder to debug, so you need to be careful to do it right.

Kubajzz · Answer 2 · 2010-07-31T06:03:00

Multithreading might help a bit if you do it properly, but there are 2 basic problems:

first, it depends on the "...." pieces of your code whether this task can be parallelized or not.

second, even if you had a quad-core processor, you could get at most 4x speedup which is not quite enough for an algorithm like this.

A quick theoretical evaluation (why multithreading does not help): the complexity of your algorithm is somemething like (m * n) ^ (levels), where m and n represent the number of iterations of the first and second loop and levels is the average level of recursion. So if your task needs in average say 10 levels of recursion to execute, you will get (m * n) ^ 10, which will probably take forever no matter how many threads you use...

I guess you will have to try harder to create a better algorithm and if it's not possible, then you'll have to be very, very patient...

Yusuf · Answer 3 · 2010-08-03T15:17:00

WOW, simply WOW, 2 for loops and recursion. It simply is hard to say with out knowing what each .... is doing. May be you can show some code with out exposion what ever you don't want to show to give more detail.

Multithreading only gives you an advantage if you can have parallel code, otherwise you are inviting bigger headache. Simply one piece of code may lock other piece and the gates of hell will open loose.

May be you can refactor what is in the ...., again with out seeing what is there it is simply hard to tell.

idenizeni · Answer 4 · 2010-08-03T13:48:00

Solution 3

Not a real solution and not sure if it will help you but, you might gain a little speed by exiting the loops as soon as possible. Can you exit your loops sooner or do you need to iterate all objects?

Posted 3-Aug-10 13:48pm

idenizeni

improve speed of recursive function

4 solutions

Solution 1

Solution 2

Solution 4

Solution 3

Add your solution here

Preview 0