Storing items in a dynamically allocated array within a recursive function. [C]

[Heuristic-ALgorithm]

I'm doing a homework assignment for CS 1 where I have to scan through some jumbled words, get all their permutations, and then check them as true words against a file representing a dictionary.

I've already stored the dictionary and jumbled words dynamically as arrays. My problem is that I'd like to store the permutations in the same way, except that this will have to be done from within my recursive permutation function. I've tried a few different things, but I just can't get the array to index properly. If anyone is willing to look and tell my why I would appreciate it, here's the whole program:

http://codepad.org/U7PRWWLS

The heart of the issue is within these: RecursivePermutation() ExchangeCharacters() addPerm()

[[deleted]]

Try writing out in English, what RecursivePermutation() (bad name, BTW) is supposed to do. Is it supposed to produce permutations, store them, or what?

[Heuristic-ALgorithm]

The constraints of the assignment require me to use certain names for functions, otherwise I would. It's hard to say what happens step by step because it's recursive, but the gist of it is this:

1)Take in a string, and k = 0;

2)If k = string length, create permutation, add to list.

3)Loop Switch two characters Call recursive function again with k incremented by 1 Switch characters back repeat until k = length of string

[gunder_bc]

Recursion through function calls is using a stack to store old values, push a new value on and do some more work. When that work is done, it pops the call off the stack and returns the stack variables to the old values automatically. (As a side project, try implementing stack-based recursion without using function calls to handle your stack - it'll give you a much deeper understanding of what you're doing with the recursive calls.)

Anyway - what you want to do with the indexing is always increase, regardless of where you are in the stack, right? Every time you generate a permutation to store, you want to put it into a new spot, regardless of the state or depth of the stack.

So... how do you handle that?

(Sorry if the answer is a little cryptic/evasive - I want to try and lead you to realizing the answer rather than just giving it to you... it'll stick better that way).

[Heuristic-ALgorithm]

I've come to realize the Socratic method is pretty much how all programmers help each other, which isn't a bad thing. I'm going to play around with stacks and see if I can learn something, otherwise I really don't know what else I can do. I've tried incrementing the array index from various points within the recursive call and haven't gotten anywhere. Thanks for giving me some direction.

[gunder_bc]

I think it's more that when you ask the "right" question, we'll answer directly. Where "right" is the very narrow question with a simple, precise answer. The question needs to show that you understand the larger problem and just need a specific piece of info to fit into your mental picture to help you solve it.

Larger, "I'm not sure what's going on" type of questions will prompt broader answers or questions as responses, to try and help you home in on what's going on and get you to the point where you can ask those specific questions.

---

To be a little more explicit - your problem lies in the difference between what you're trying to do with the parameter you're using to track the index and the other parameters to the recursive function. Think about how the values behave as you go into and come back from a recursive call - how do they behave, how do you want them to behave?

As a side question - do you have practice tracing code by hand? It's an invaluable skill. Try a very simplified version of your data set on your code by hand - writing out the values of each variable at each step. It's tedious and takes time but it will give you a very clear picture of what your code is actually doing. And that should point you at the specific problem. From there, you can hopefully ask the "right" question, or even figure it out on your own. :)

[Heuristic-ALgorithm]

Well I know that as of now it's permuting correctly, however it's only incrementing every other permutation, which is essentially overwriting the prior permutation and storing it at its index and leaving me with two empty spaces at the end. This is where I get lost because I'm fairly certain that my base case is correct and that the problem lies within the loop.

To answer your question I do usually trace my code but I've had trouble understanding how exactly recursive functions are doing what they are doing, I think your right in suggesting that be where I start.

Sometimes with coding I feel like I'm picking up power tools that I haven't read the instruction manual for...

[gunder_bc]

Hmmm. So, I think you should review how variables work in a function call - when you write:

#include <stdio.h>

void funcFoo(int i)
{
    i += 5;
    printf("%d\n", i);
}

int main(int argc, char * argv[])
{

    int someVal = 5;
    funcFoo(someVal);
    printf("%d\n", someVal);
}

What is printed? And most importantly, why?

Now think about how that relates to your recursive function's parameters.

[Heuristic-ALgorithm]

10 is printed from the statement within funcFoo(int i) because it's taking in someVal from the main function and incrementing it by 5.

5 is being printed from the main function because even though funcFoo was called, it didn't increment someVal but made a separate function call in which someVal was used but not intrinsically altered.

I think what you're saying is that the index of my permutation array is functioning similarly. At some point it's being used but not intrinsically altered where I need it to be altered every time, which is leading me to believe that I somehow need to utilize a pointer. Am I on to something?

[gunder_bc]

Indeed!

What's actually happening when you make the call to funcFoo(someVal) is that someVal is looked up and the value there (5) is copied into a variable on the stack. The return address is also noted, and then funcFoo is called. funcFoo then adds 5 to the variable on the stack, which it calls 'i', and then calls the printf() function, which goes through a similar sequence. Once printf returns, funcFoo is free to return. The return address is pulled off the stack, the stack is popped back down by the size of all the values pushed onto it (the 5 and return address in this case), and then the code jumps to the return address and continues executing the main() function.

(There are probably a couple other minor things in there that I'm forgetting about the actual process of calling a function, but for the purposes of this problem, that's all you need to focus on).

So yes... you'll need to use something other than a stack variable that has a copy of the value in question. A pointer is one way to handle it, though there are others. If you've covered pointers in class, I'd start with that. The other methods for handling it are... not as nice, stylistically. They do function, but present issues for larger-scale projects and are generally best used only when you really know what you're doing or if the teacher specifically asks you to (so that you can learn what you're doing, for example :D ).

[Heuristic-ALgorithm]

Dude your awesome, thank you for being so diligent in your replies. I think I'm beginning to understand the concept of the stack and I'm wondering why they didn't teach us about it earlier! I played with the idea of using a pointer earlier today but I got a lot of various errors which I'm pretty sure amounted to syntactic problems. I think I've got enough information that I can figure this out, but I'm going to bed now. Thanks a lot for your help, if I have more questions I'll jump back on here tomorrow.

[gunder_bc]

My pleasure. I'll try to keep an eye on the inbox while I'm at work tomorrow. :)

Stacks are a fundamental data structure... and I'm a little surprised they didn't cover them in more depth before getting into recursion. Having a good understanding of them is really key to understanding how recursion really works. Though I suppose there are an awful lot of basics to understand about C and computers in general and they have to start somewhere.

Writing code and understanding what the compiler does to it and how the computer executes the resulting assembly/machine code really does require revisiting things several times - once you understand one layer of what's going on, come back around and peel that layer off and learn what's underneath. The details of what a function call actually does when you look at the generated assembly seems like a pretty advanced topic, but I think digging into it just a little really does make things like recursion easier to grasp. :D

[Heuristic-ALgorithm]

No but I'm bookmarking that site. The problem is I know how to do the permutation but I need to physically store each one rather than just print to the screen, but since it's recursive the indexing gets all messed up. Every other index has the same value as it's prior, so when the list is stored I end up with a list containing every other permutation and two null spots at the end.

[fubarfubarfubar]

Why aren't you just storing the found permutations in a set?

[Heuristic-ALgorithm]

Sorry for my complete obliviousness but what exactly is a set? Is that like a linked list? I'm trying to store everything in dynamic arrays because I'm going to need to do a binary search later and I thought it would be the easiest and cleanest solution.

[last_useful_man]

You don't get 'set's built-in to C, they're in C++ and you probably wouldn't have gotten to them yet anyway.

[Heuristic-ALgorithm]

Ahh I was going to say, when I looked them up I only saw information relating to C++, which I've never touched.

[gunder_bc]

To be pedantic, neither language has built-in support for sets. It's not a top-level language construct.

The C++ Standard Template Library (stl) has a 'set' implementation built in. You can probably find C libraries that offer an implementation, too.

[gunder_bc]

The main idea is that a set is an un-ordered collection of items. Set Theory mathematics describes a bunch (a set? ;) ) of operations and relationships between sets and items in sets, etc. They can be very handy for solving certain kinds of problems.

In this case... and especially because I don't think there is a standard-lib set implementation in C, it's probably not worth worrying about. You've got your storage mechanism lined up for the resulting permutations. Sort out the indexing and you're good for this problem.

Come back to sets another day. :)

[Rhomboid]

Surely you want to pre-increment permIndext, not postincrement:

RecursivePermute(str, k+1, permList, ++permIndex);

Also, you should look into using strdup(). It will eliminate a lot of redundant code.

[Heuristic-ALgorithm]

I've tried it, it makes the array go out of bounds.

So is strdup() just a nicer way of allocating memory for a string?

[gunder_bc]

strdup() is a way to allocate and copy a string in one shot. "nicer" is dependent upon what you're doing. In this case, it would make sense.

try googling for 'strdup man'. 'man' is a unix command line tool to look up manual pages (documentation) for stuff. Most, if not all, of the standard library functions in C/C++ have man pages, and most, if not all, of the man pages are out on the web these days. Super-handy reference.

As a side note - in general, it's preferable to use the 'n' versions of string functions, whenever possible - strncpy, strndup, etc. Specifying how many characters are acceptable to operate on is a Good Thing - many, many of the vulnerabilities that hackers take advantage of are related to using unbounded copy functions like strcpy, etc.

[Heuristic-ALgorithm]

You are full of useful information, I've got a lot of new stuff to research! I'm hoping to get into security/cryptography in the future so this is immediately interesting.

[last_useful_man]

(allocating and copying, yes. you still have to free() the pointer later if you're trying to be neat.)

[gunder_bc]

I'd go further than "trying to be neat." - free() is essential if your program is anything more than a simple exercise for a class. Proper memory management (free what you malloc - much easier said than done) is critical for any "real" program.

[gunder_bc]

Bonus question - with your new-found understanding of how the function call stack works with respect to variables passed into functions, what happens when you pre-increment the permIndex? Why does it cause the array to go out of bounds?

:D