Friends,

I have a doubt whether recursion is efficient or not.
For example, consider this code to find the power of one integer to another:

I think it consumes memory and time more than if we just use a for loop.
What do you think?

Thank You,
Paramesh.

[quote=Paramesh]Friends,

I have a doubt whether recursion is efficient or not.

Usually, recursion is not efficient in terms of stack and system overhead.
Think about a recursion to calculate the factorial of a number.
You will have n-1 recursion calls, each one of them pushes to the stack it's arguments and process id.
Also, notice that each recursion call generates a copy of the function in the memory.

Recursion is used by me to solve specific types of problems (usually math problems).

Recursion is very important, sometimes, as the iterative equivalent may be very hard to implement (I guess you know every recursive function has an iterative equivalent).

Kobi.

P.S Paramesh,
Your finals are this coming week too, right ?

No, it's not efficient. And where a loop can be used it's terrible.

Where recursion is best used is for algorithms that generate sub-values that are used to get a final value (calculus comes to mind) or when certain states of processing can be best accomplished by a "start over" concept (directory traversal, maze traversal, 15-puzzle solutions).

I'll add Dynamic programming to the list.

Kobi.

I understand that, due to popular demand, the SAT tests were changed recently to eliminate most of the dreaded "simile" questions. (You know: sock is to foot as glove is to hand---that sort of thing.) Too bad, since I would have said:

Recursion is to efficiency as fish is to bicycle.

In other words, what the heck does one thing have to do with the other? Recursion is an unbelievably powerful technique for certain problems, but it's kind of hard for some of us to get our brains around (and I'm not being coy or modest here, I definitely include "me" in "us"). Things like quicksort simply can't be expressed or implemented without recursion. If you had never done anything with recursion, you might find it kind of hard to get the idea of the recursive "divide and conquer" technique of quicksort, and how to implement the technique in a program.

(And here I speak from the experience of seeing an implemantation of quicksort in FORTRAN some years ago. The language and computer architecture of the time simply had no built-in mechanisms for recursive subroutine calls or any other kind of re-entrancy. They had to implement a program stack and local variables with (global) arrays to explicitly kept track of things that are automatically done with C. The results were worth the effort since the application itself really needed something like quicksort to be able to finish before the next ice age. Bubble-sort enthusiasts need not apply.)

Since it is difficult for many of us, instructors and books usually use simple examples that try to make it easy to trace exactly what the routine is doing, even though the problem itself is not well suited to a recursive solution in terms of efficiency (or anything else, for that matter).

You know, things like calculating factorials. Things like finding the minimum element in an array. Things for which it is easy to check the results, and things for which it's easy to put in debugging statements to see the progress.

I have seen people deride their Computer Science instructors for making them calculate factorials by using recursion. I think the students missed the point. The point was (I assume) not to teach them that the "best" way to calculate factorials is by recursive techniques, but to give a simple, easy example that gives a flavor of how to apply recursive techniques with a C program.

Many of my mathematician friends embrace recursive definitions for things like factorials. Simple; elegant; precise

0 Factorial = 1, and N factorial = N times (N-1 Factorial) for positive integers N.

But when giving the explanation to non-mathematicians, they always seem to have to revert to explaining the meaning in terms of the non-recursive and more-or-less intuitive algorithmic approach of "multiplying together all of the positive integers up to and including N"

Which is more efficient: a loop or recursion? Which is better for a fish: A bicycle?

Here's an assignment. How would you solve it using recursion? How would you solve it not using recursion? Is efficiency a factor in your decision of which technique to use?

Given a positive integer N.

Print out all permutations of the numbers 1, 2, ..., N

For example: With N = 3, the output could look like this (but the program can output them in any order):

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Write a program that works for any positive integer N (to keep it printable, maybe you would limit it to N < 20, but the program should not have any fundamental limitations ---other than program memory and limits of integer representation--- for any positive integer N).

Do something like this, using recursion, then go back to the "factorial" problem for which recursion seemed so, well, unnatural, and see if it makes more sense. (I know, this is kind of backwards: do the hard one first then go back and see how it makes the easy one easier.)

Regards,

Dave

"To err is human, to forgive: devine"
---Alexander Pope

"To iterate is human, to recurse: devine"
---Anonymous mathematician/programmer in 1958
(I know who he/she is, but I promised not to tell, since he/she now thinks it's too frivolous.)

"To err is human, but it feels devine."
---Mae West

Wonderful assignment Dave.

I'm too sleepy now and try to solve the assignment tomorrow.

Thank You,
Paramesh.

Dictionary ...

Well, Any recursive solution has an iterative equivalent - Including quicksort.

I don't underestimate the usage of recursion. It is in many cases the logical solution (as in quicksort or the knight-tour we discussed several threads ago).

It is simply that a task that is being performed recursively will usually be less efficient (in terms of system overhead - Many function calls) then it's iterative equivalent, and that was Paramesh's topic.

Shabat Shalom,
Kobi.

I'm glad you mentioned this. My statement wasn't very precise, was it? (Depending on how you interpret it, some might even say it was wrong.)

The intent of the statement was to emphasize that some things are conceptually recursive in a way that is more difficult to express without resorting to recursive language.

Definition and calculation of factorials could go either way (conceptually, that is), but it's easy for me to believe that implementation of factorial calculation by iteration makes better use of system resources (fewer function calls, less stack usage) than by use of recursion.

I don't think the same can be said for quicksort. Yes, you can twist your thinking and implementation of quicksort to do it without recursion (heck, you can do it on a Turing machine if you really want to --- but you've really got to want to). That's why I mentioned that I had seen the example with FORTRAN. Articles on iterative quicksort make good reading and are sometimes quite challenging, but the conclusion for ones that I can recall (vaguely, that is) was that the iterative techniques were slower, and in fact didn't always use fewer system resources than the recursive method.

From my point of view, one of the biggest drawbacks for recursive techniques is that sometimes it is hard to tell in advance just how much will be required of system resources. (How deep will it go in the worst case?)

In small systems (embedded systems running Linux, that only have a few tens of Mbytes of memory) there is a real danger in turning loose a program with unknown memory requirements. And the memory requirements might depend on what data are actually being processed, so that no amount of testing can convince me that it will always work. That's unacceptable, especially if there is an alternative method whose worst-case behavior is easy to analyze.


But "usually" doesn't feed the bulldog. (Don't try to look that up; it's a regional colloquialism in certain parts of the U.S.)

Even "almost always" may not be good enough.

Recursion is just one more tool for our toolbox. Usually efficiency has nothing to do with whether I choose recursion or not.

Regards,

Dave

Besides, if you start out with the most nearly optimal solution that you can come up with, how are you going to optimize later? (When the boss says, "make it faster, smaller, more robust.")

This assignment has blown me off.
I am still unable to find how to do this.

Please give me a hint.

So far, i have thought of:
Use two global variables, and
Creating a character array to store the values upto the number N using dynamic memory location.
The recursive function should have the definition something like:
where n can be used for some inner calculations.

Thank You,
Paramesh.

I don't remember exactly what I did the first time I encountered this little puzzle, but I will try to simulate the sequence of events, given current context (in other words, if I had known then what I know now):

Since iterative techniques are "easier" to teach than recursive techniques, many (most?) programmers look for iterative solutions.

Lots of times I look for specific solutions, and then try to generalize them. So, suppose that someone wanted to print all permutations of members of the set {1 2 3}.

One of the first things that comes to my mind is something like the following:


Now, this is simple enough, but there are a couple of problems with this.

Here's the output:


1. Doesn't satisfy the program requirement to print permutations. It actually prints all combinations. That is, it prints all triplets whose first element is a member of the set {1 2 3} and whose second element is a member of the set {1 2 3} and whose third element is a member of the set {1 2 3}.

You can count them if you want: there are 27 triplets printed, and (27 = 3 to the power 3).

2. I don't see how to generalize it so that the same program can print permutations of members of the set {1 2 3 ... N} for any user-specified positive integer N.

Note that objection number 1 can be overcome by putting some kind of filter in place that eliminates any triplet with repeated digits. Maybe something like this:


This time the output looks like:

Now, that's right: the six permutations are generated and printed. Would you like to stop and analyze this for efficiency now? Well I wouldn't because (and this is multiple choice):

1. It works, and "efficiency" wasn't part of the Program Specification.

2. Well, as written it actually it only works for N = 3, and the program is supposed to work for N = any positive integer, and I don't see how to make it do that, so why waste time determining some "efficiency" number on something that I probably won't be able to use anyhow.

3. All of the above.

Now, in keeping with my philosophy of "Get it Done now; Optimize later", I will (temporarily at least) abandon the iterative approach and consider recursion.

How would I generate the permutations in a recursive program? Now I show my true nature: goal-oriented, bottom-up. (That doesn't always work, you know, so don't be dogmatic about it!)

Start with the desired printout and figure how to do it with a program. Remember that the order in which the permutations are printed is not specified. As a matter of fact, the problem statement specifically said that the output could be in any order. So the results in the following examples don't have to be reproduced exactly, just as long as all permutations are printed.

N = 1:

N = 2:

N = 3:

Now, considering the nature of the problem (has to work for user specified value of N), it is apparent that the results can't be printed with a single printf statement of the form printf("%d %d %d ...);, right?

So, however we generate the permutations, it looks to me like we will store the elements in an array and print out the members of the array (either as we go, or after all of the elements are in place for a given permutation).

I could just put the char representation of the digits into a string (an array of char) and print out the string at the end (with printf("%s);)

I could just put the integers into an array, say numbers[N], and print the elements of the array. Man, I'm just dying to write some code, even though I always tell people at this point that it's way too early to start writing code. I'm more of an "integer" guy than a "string" guy, so my print routine looks something like:



OK, now I know how to print out each permutation, assuming the elements have been put into numbers[0], numbers[1], ... numbers[N-1]. But how the heck do I get them there?

Look back at the output for N = 3. I see it this way (keeping in mind that I am now tuned into the "recursive" thing):


Where we started with {1 2 3}, and the first two outputs are obtained like this:
leave the first element set to 1, and print all permutations of the elements {2 3}

The third and fourth outputs were obtained like this:
swap the first and second elements (so the first element is 2), and print all permutations of the elements {1 3}

The fifth and sixth outputs were obtained like this:
swap the first and third elements of the original array (so the first element is now 3) and print all permutations of {2 1}

("Man," the programmer in me is saying, "that looks kind of like a loop and a recursive call, doesn't it?")

Now, here's the point where some of us have to make a giant step to cross the gap from the specifics for N = 3 to a recursive algorithm for any positive integer. And for those poor souls who never had a Computer Science instructor force them to calculate factorials with a recursive function, this gap becomes an almost uncrossable crevasse --- and it's a long way down.

So: here is a possibility:

We start with an array of ints containg the values {1 2 3 ... N} (set up in the main() program before calling the recursive function).

We create a permution by rearranging (swapping) the elements in a certain way so that when we get to the last position, the permutation is ready to be printed.

So, we will have an argument to the recursive function that indicates the current position within the array where we are going to put the next element.
Let's call that argument "place".

When we get into the recursive function with "place" equal to N, we know that all of the elements of the current permutation are there, ready to be printed.

So the exit part of the function looks like:


Now, the recursive part of the function (if "place" is not equal to N), can have the following functionality:


See what's happening? For the elements of the array, we step through the array, and at each "place" in the array, we are using the recursive function to print out all permutations of the digits to the right of us.

Try it again for N = 4 (pencil and paper, remember --- no code yet).

How do I get started? Well, in the main() function, I set array values to {0, 1, 2, ..., N-1} (with a program loop, after the user has entered "N"). Then I call the recursive routine with "place" = 0. Then it's off to the races.

Now, that's recursion.

Your thought process might be quite different, but however you get to this point, this is ready (I claim) for implementation.

I implemented a recursive function based on these ideas and it works for me and it satisfies the requirements.

If you do this (or something completely different) you might want to look at efficiency at this point. I choose not to. Why? Because I don't have to, and you can't make me. Nyaa, nyaa, nyaa.

But, seriously, I am so relieved at actually having a working solution that I think I'll quit right now. If the boss comes back and says, "That's pretty good, but I really wanted you to do it without recursion," then I'll probably go back and try it.

If you want to return the investigation of iterative techniques, I say: go for it!

Maybe, unlike me, you didn't abandon it in the first place and you already have an iterative solution. If so: I say, "Hoorah for your side!" It wasn't intended to be a contest, you know, and if someone wants to make it a contest, I'll let others participate.

Just remember, if you want a contest, that means that someone will have to decide who is the winner.

And that means that some kind of metric has to be defined. Sometimes points are given (or deducted) for code size, sometimes for execution speed, sometimes for total elapsed time from problem statement to successful execution, sometimes for quality of documentation, etc., etc.

Sometimes these points are in the form of dollars (or shekels or euros or whatever) on a paycheck. The problem is that someone has to define ahead of time what the criteria are for judging the winner.

Ever since the dawn of the computer age, Managers (that's managers with a capital M) have struggled to find a metric for software productivity. You know, something that you can enter into a cell in a spreadsheet that plugs into a formula that says how much this person is worth to the company.

The idea is that the Manager won't actually have to have any clue whatsoever about what that particular humanoid does all day every day when he/she comes to work --- it's just a little cell on a big spreadsheet. Plug in "something" crank out the "answer".

I'll be generous and say that the results (of trying to find a metric for software productivity) are not always consistent with the actual value of the individual (and that individual's effort) that is supposedly being evaluated for purposes of reward/punishment.

Regards,

Dave

(I was at a local drug store the other day looking for an item that was advertised as being on special. I wish I could be given the opportunity to enter a number into the productivity spreadsheet cell of the store Manager, who blamed non-availability of the advertised item on "computer error". Yeah, right!)