[error401]

Quote:

Originally Posted by Arainach /img/forum/go_quote.gif First off, do you HAVE to use recursion for the entire program? Specifically, that Factorial Program will choke on anything larger than 20 or so. It's easy to use a table to linearize factorial lookup as such: Code: [left]int factorial(int x) { int fac1=1,fac2=1,fac3=1; for(int i=x-1; i>0; --i) { fac3 = fac1 + fac2; fac1 = fac2; fac2 = fac3; } return fac3; }[/left] That'll fun a LOT faster than the recursive function. Recursion, done right, can be the most efficient solution. But very, very rarely is it ever so. As to the permutation problem: I'll take a look at it now.

You're right of course, though this limitation is really due to the way the language works than an implicit disadvantage to the recursive solution. A tail recursive function in a language like Scheme can certainly be as fast or faster than an iterative function in a language like C. In most cases performance is not important enough to sacrifice the clarity of the recursive solution to a recursive problem. This should be clear from your example function, which takes much more analysis to understand (and I'm far too lazy to actually read through this to see if it's correct, though I do remember a similar solution existing). I don't recommend this approach, especially for someone new to programming, unless the performance of the particular function (and its callers) is a critical system parameter.

In your particular example, the performance difference is not due to the lack of recursion, but the elimination of the lengthy multiply instruction that removing the recursion allows. In fact, the recursive example will generate less instructions than the loop will (and makes far fewer hits to memory, though this might fit into the registers on a CISC platform like i386). C will choke before 20! with any function unless you use big integers anyway, 12! is the largest that will fit into int32, and with a stack only 12 calls deep, especially with tail call optimization you won't be able to measure a difference. Using big integers, multiply is probably even slower than it is on-cpu, and the merits become apparent. But who really needs to compute factorials at runtime anyway? In a real application you'd probably want a lookup table unless you're a numericist or something. Writing a function like this is an exercise is using recursion.

 

[ilovesocks]

Quote:

Originally Posted by error401 /img/forum/go_quote.gif Java's standard library is heavily over-engineered in my opinion. Just performing simple tasks like reading from STDIN requires the instantiation of several objects, accessing class-scoped static variables and other things. Even doing some very basic things in Java requires instantiating complex container objects and other similar tasks that can't be properly explained until a more advanced course in data structures or specifically OO. Not only that, its strict adherence to OO methods forces the student to take on the entirety of OO design (including generics, the pitfalls of using references, object instantiation, more complex scoping etc. etc. etc.) when they should be learning the basics about loops, how the stack works and the like. Because of the complex standard library, it forces the instructor to gloss over extremely important concepts in the interest of keeping things as simple as possible for the student. For example, when I took an introductory class in Java the instructor didn't even explain what all the keywords in the classic 'public static void main(String[] args)', despite many students asking (citing that it would confuse many) until more than halfway through the course. Those with existing experience in any language were asking questions the instructor didn't want to answer so he didn't confuse the rest of the class, and both sets of students end up out of the loop. I had prior experience in OO and didn't have a problem with this, but most students were very confused by all the hoops they had to jump through. Further, Java has its own pitfalls that I don't think are any easier to resolve than those in C++ - and IME are much more likely to be runtime errors rather than compile time errors. I also extremely dislike that it even has types that aren't objects, and all the workarounds required to deal with them. It's supposed to be a strict OO language and yet it has variables that aren't objects?! I know they did this for performance reasons, but it's still a huge pain in the ass. This is a bit better in Java 1.5 with autoboxing, but then you run into other invisible issues... It's not fun for me, and I know what I'm doing, I'd hate to be a student writing my first program running into these kinds of things...

I just took my first programming class (Intro to Java) last quarter, so I know exactly what you're talking about; I don't know what "the stack" is (I'm guessing it's some sort of structure of memory) and for the first two thirds of the class, [public static void main(String[] args)] was "magic" (the professor's exact word for it. But she was really cool - my favorite professor so far). We didn't learn about sending input into the program from the command line, so we didn't take advantage of the String[] args parameter.

I'm taking a discrete mathematics class now and we're learning Haskell, which I think would make a good starting language for CS, since there's almost no overhead code over your functions (just [module Module where] - easy enough to understand!), and recursion is so simple - finding the greatest integer in a list is as easy as [maxInt (x:xs) = max x (maxInt xs)] plus the base cases [] and [x].

 

[error401]

Quote:

Originally Posted by ilovesocks /img/forum/go_quote.gif I just took my first programming class (Intro to Java) last quarter, so I know exactly what you're talking about; I don't know what "the stack" is (I'm guessing it's some sort of structure of memory) and for the first two thirds of the class, [public static void main(String[] args)] was "magic" (the professor's exact word for it. But she was really cool - my favorite professor so far). We didn't learn about sending input into the program from the command line, so we didn't take advantage of the String[] args parameter. I'm taking a discrete mathematics class now and we're learning Haskell, which I think would make a good starting language for CS, since there's almost no overhead code over your functions (just [module Module where] - easy enough to understand!), and recursion is so simple - finding the greatest integer in a list is as easy as [maxInt (x:xs) = max x (maxInt xs)] plus the base cases [] and [x].

Haskell is really neat from what I've read about it, but I've never actually tried it out. I like Python because its syntax is also quite loose and not too verbose, but it still allows for decorators to acheive the same functionality. It also has elements that allow for fairly easy use of any programming methodology - all the libraries are OO, and object orientation is well supported and the 'default' methodology, but there are also many constructs that are useful in functional style, and unlike Java it doesn't force you to create your own classes (though everything is an object [including functions, literals etc.]). It's a pretty nice language, you should check it out. Just for fun, to counter your example, this is built-in in Python. The 'max' builtin function takes any sequence as input and returns the 'largest' (you can use your own data types and define the comparison function) item in the list. So: max(x) is it . Recursion isn't as nice as Haskell though with its implicit definitions. Also, IIRC Haskell does type inference to do strong typing with no syntax, which is really neat.

The 'stack' is indeed a memory area. It's the area where any function-local data is stored. Each time you call a function, a stack 'frame' is created that contains space for all of the variables local to that function, as well as the return address in calling function. When you return, this area is deallocated and the processor is instructed to jump to the return address indicated, moving the program flow back to the instruction after the initial function call. This is the mechanism that allows recursion to be possible, as it allows multiple copies of the same function to have different states simultaneously. It often causes problems in heavily recursive programs though, as the size of the stack is finite and defined at the time the program is started, and usually can't be resized. Since you're allocating space each time you call a function, and only freeing it when you return, you can only go so 'deep' in the recursion before a stack overflow occurs and your program crashes. In the tail recursive case this extra memory usage can be eliminated though: because we can prove that no local variables are accessed after the recursive call, we can effectively use the same stack frame as before (since the return address doesn't change, and we will never need the local variable values again) and just reinitialize it.

 

[seanohue]

Bah, well what I did did not work. I screwed the recursive step up by thinking that for loops did not reset when I called the next function. I thought of a way to make it work non-recursively but my task is obviously to do this recursively.

Code:

[left]#include <iostream> #include <vector> using namespace std; typedef vector<int> vint; vector<int> insert(vector<int>& v, int pos, int s) { int last = static_cast<int> (v.size() - 1); v.push_back(v[last]); for (int i = last; i > pos; i--) v[i] = v[i - 1]; v[pos] = s; return v; } vector<int> erase(vector<int>& v2, int pos2) { int last_pos = static_cast<int> (v2.size() - 1); v2[pos2] = v2[last_pos]; v2.pop_back(pos2); return v2; } vector<vint> permutations(vector<int> vec) { vector<vint> supervec; int n = static_cast<int> (vec.size()); if(n == 1) { supervec.push_back(vec); return supervec; } else { for (int i = 0; i < static_cast<int> (vec.size()); i++) { vector<int> remain(1); vector<int> temp = vec; remain[0] = temp[i]; temp.pop_back(i); for (int j = 0; j < static_cast<int> (temp.size()); j++) { supervec.push_back(insert(temp, i, remain[0])); } permutations(temp); } } return supervec; } int main() { cout << "Enter the an integer (not 0)\n"; int x; cin >> x; vector<int> vec(x); for (int k = 0; k < static_cast<int> (vec.size()); k++) { vec[k] = (k + 1); } vector<vint> supervec = permutations(vec); vector<int> tempvec; for(int i = 0; i < static_cast<int> (supervec.size()); i++) { tempvec = supervec[i]; for(int j = 0; j < static_cast<int> (tempvec.size()); j++) { cout << tempvec[j] << "\n"; } } return 0; }[/left]

I have created two functions, the insert and erase which insert a value (s) at an index (pos) and erase a value at an index (pos2). The remain vector that is of size 1 in the first for loop takes the i'th index of the of the temp vector which is the original vector copied. I think I am missing some fundamental idea of recursion and not realizing something.

 

[seanohue]

Quote:

Originally Posted by seanohue /img/forum/go_quote.gif Bah, well what I did did not work. I screwed the recursive step up by thinking that for loops did not reset when I called the next function. I thought of a way to make it work non-recursively but my task is obviously to do this recursively. Code: [left]#include <iostream> #include <vector> using namespace std; typedef vector<int> vint; vector<int> insert(vector<int>& v, int pos, int s) { int last = static_cast<int> (v.size() - 1); v.push_back(v[last]); for (int i = last; i > pos; i--) v[i] = v[i - 1]; v[pos] = s; return v; } vector<int> erase(vector<int>& v2, int pos2) { int last_pos = static_cast<int> (v2.size() - 1); v2[pos2] = v2[last_pos]; v2.pop_back(pos2); return v2; } vector<vint> permutations(vector<int> vec) { vector<vint> supervec; int n = static_cast<int> (vec.size()); if(n == 1) { supervec.push_back(vec); return supervec; } else { for (int i = 0; i < static_cast<int> (vec.size()); i++) { vector<int> remain(1); vector<int> temp = vec; remain[0] = temp[i]; temp.pop_back(i); for (int j = 0; j < static_cast<int> (temp.size()); j++) { supervec.push_back(insert(temp, i, remain[0])); } permutations(temp); } } return supervec; } int main() { cout << "Enter the an integer (not 0)\n"; int x; cin >> x; vector<int> vec(x); for (int k = 0; k < static_cast<int> (vec.size()); k++) { vec[k] = (k + 1); } vector<vint> supervec = permutations(vec); vector<int> tempvec; for(int i = 0; i < static_cast<int> (supervec.size()); i++) { tempvec = supervec[i]; for(int j = 0; j < static_cast<int> (tempvec.size()); j++) { cout << tempvec[j] << "\n"; } } return 0; }[/left] I have created two functions, the insert and erase which insert a value (s) at an index (pos) and erase a value at an index (pos2). The remain vector that is of size 1 in the first for loop takes the i'th index of the of the temp vector which is the original vector copied. I think I am missing some fundamental idea of recursion and not realizing something.

bump

 

[error401]

Okay, I see a few immediate issues with the code itself, and I'm not sure I understand your approach here.

First of all, insert and erase are both implemented in the STL as part of the vector class. Use their implementations, they will be much more efficient, and you won't have to worry about bugs

. The only problem is that you'll need to use iterators rather than integers to specify positions. You can do this by using vector.begin() to get an iterator to the start, and adding an integer to get a new iterator for the correct position. See SGI's STL reference for some (rather sparse, but the best I've found) complete documentation on what the STL can do. They delineate which functions are SGI-specific, so this should apply to any development environment as long as you avoid the SGI functions. If you're using GCC, the standard development libraries use SGI's implementation.

Another thing that will definitely be a problem is that your inner loop is infinite! The conditional (j < static_cast<int> (temp.size())) is evaluated for each loop run, and you're adding an element in each loop run as well, so 'j' and 'temp.size()' will increase in unison, with j always being smaller. You probably shouldn't be modifying this vector in the loop anyway. If you want to embrace the STL's power, you could use iterators instead of integers to control the loop flow, but this is not strictly necessary, it just allows you to dereference the iterator to access the current element instead of accessing the element with the [] operator. (For fun, here's what a 'for each' type loop looks like using STL iterators: Code:

[left]vector<int> v; // to show the type and name, obviously it would need some data // v::iterator is read and write, while v::const_iterator should be used if you're only reading for (v::iterator i = v.begin(); i != v.end(); i++) *i = dosomething(*i); // * is the dereference operator and will get/set the value at i's position in the vector[/left]

This same code can be used with almost any STL container (I believe set is the only exception, but YMMV) without modification. Aren't templates great!
)

Finally, the vector.pop_back() function doesn't take an argument. It always pops the last element off the vector (as its name implies). If you want to delete an element that's neither at the front or the back here, you need to use vector.erase() instead.

Now, with the code problems out of the way, let's look at your algorithm. I think you're getting there, but this code isn't going to work, and I'm a little confused about what you're trying to do with remain and temp. Are these vectors supposed to contain the remaining characters and the current permutation, respectively? If so, you should be able to instead do this just by copying the input to 'remain', and then popping the last value and pushing it into temp.

Also, you probably only need one loop here, you should be looping through the available values and for each value, remove it from the list, create a new permutation with it added, and make the recursive call, then restore that value to the available list.

I'm off work so that's all I have for now. Good luck.

 

[seanohue]

nvrmnd.

 

[vagarach]

Here is a nice graphical illustration of one algorithm:

From http://www.bearcave.com/random_hacks/permute.html

There are several algorithms with c++ code at that site, so don't visit it if you don't want to taint/predetermine your thought processes.

 

[error401]

Interesting algorithm.

For anyone that looked at my STL example, I made the error I always make doing this outside of an IDE: the iterator type can't be obtained from the instance, only from the type itself. This has always been a beef for me, and something I just can't seem to get into my head - but it's a language limitation and there's not much to be done about it. Serves me right for not at least compiling my examples first...

The correct code is thus:
Code:

[left]for (vector<int>::iterator i = v.begin(); i != v.end(); i++) *i = dosomething(*i);[/left]

 

[Arainach]

As a general rule, types have to be declared at compile-time. The tricky part comes when you realize that due to inheritance rules, there's no way to know the exact type of a variable that will be passed to something. What if you have a class that inherits from vector but has an iterator that works differently? Etc. - these decisions have to be specified beforehand.

 

[error401]

Quote:

Originally Posted by Arainach /img/forum/go_quote.gif As a general rule, types have to be declared at compile-time. The tricky part comes when you realize that due to inheritance rules, there's no way to know the exact type of a variable that will be passed to something. What if you have a class that inherits from vector but has an iterator that works differently? Etc. - these decisions have to be specified beforehand.

Yea, I understand the limitation and why it exists, I just can't convince my brain to remember this when I'm writing code. I guess my brain is just lazy and doesn't feel like remembering that it needs to type out the whole data type with template parameters every time I need an iterator. Dynamically typed C++ ftw!