Recursive Programming General

Since I don't know how this board doesn't have one yet when basically every other programming board on the internet does, this thread is devoted to all your recursive programming needs and desires. Post or request sample code and scientific papers/articles about recursive programming, compare your recursion experiences with different languages, and discuss everything from whether recursive programs are better or worse than iterative programs for practical programming tasks to the computer science implications of Turing-complete languages written entirely with recursive functions. This thread was born out of a question I had in >>6147 regarding how to create recursively programmed cellular automata, and on realizing no thread like this existed here, I thought it was needed. We can answer that and many other questions here.

Recursive programming is just regular programming. Seems kind of dumb to have a thread specifically for recursive programming .

I thought people would jump on this right away even if they don't often use recursion, because it's such a singular topic. Maybe that was a little off base, so I decided to put together a full introductory post that goes through some of the most common points of recursion discussion so we can get them out of the way and get to people's specific questions, since there's a considerable amount of resources for recursive programming online already. Plus, I didn't want to bog down the OP's statement of purpose. That goes against the idea of recursion because we're not repeating all the points of every recursion thread on every board in history, but recursion is generally supposed to be used sparingly, so maybe the thread doesn't need to be completely recursive. Still, I'm hoping that in a couple months or so this thread will be both an excellent repository of recursive programming tips and a stupefyingly massive supply of recursion jokes. I guess I'll start things out with a couple of articles and my own perspective on recursion. I'm largely trying to avoid just using stuff you could find on the first page of your chosen search engine's results for recursive code, but there are some noteworthy exceptions, such as this: https://www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches This article gives a good summary of the basic ups and downs of recursive programming and provides some example code, so it's one of the best things you could find to kick off a thread like this. I should also note that the bit mentioned in the OP about the Turing-completeness of entirely recursive programming languages is near the top of the Wikipedia article on the subject, but it stuck out at me because it's pretty important when anything is Turing-complete and yet my classes never mentioned it. Then again, it's been years since I was in college, so maybe things have changed since then with regards to the way recursion is taught. In an effort to curb the severe memory use, we should mention the practice of tail recursion right off the bat. You can often optimize recursive code by placing the recursive function call at the end. This causes some compilers to internally convert it into iterative form. Since you run the risk of stack overflow in many recursive programs, this is a good option to keep in mind. Not all languages or compilers support it, though. Other than that, random people on the internet have said recursion can be very useful in game development for pathfinding and some other important things, which is great because vidya is love, vidya is life. Sadly, I don't know any game devs. Anyone from the game development thread want to tell us more about this? Anyway, here's a piece on recursion that goes into detail about tail recursion: https://eli.thegreenplace.net/2017/on-recursion-continuations-and-trampolines/ If you're not using tail recursion or some other similar method, you need to make sure that your recursive program isn't meant to handle a very complex problem space so you don't need the stack for much. We can discuss all potential methods of optimizing recursively written programs here. What I wrote in the OP is based on what I've done in programming classes, which I talked about a bit in the CA thread. We were taught about it very briefly and basically told not to bother with it because it's computationally inefficient for most situations. I've talked to expert programmers who've been at it for 20 years and many of them have said they've never encountered a situation where recursion was desirable. I myself have only used it a handful of times in the programming I've done since college, just when I needed to implement quicksort into something, so my skills with it aren't exactly top of the line. I only became interested in taking a serious look at it when the idea of using them with CAs occurred to me, but recursion is a huge subject and I think I may have missed something important by not devoting more time to it sooner.

>>6266 Recursively written programs are a special class of programs with traits distinctive enough to warrant their own thread, most notably the extreme ease of constructing them, albeit at the expense of performance if not done properly. People in various communities have threads about different programming paradigms all the time, when a paradigm is really just a way of thinking about how to write programs. There's arguably less distinction between programming paradigms in general than there is between iterative and recursive programming.

>>6281 Of course, this shouldn't be construed to imply that every program with a recursive function will be written entirely in recursive functions. Certain paradigms like functional programming lend themselves to that, but you can write programs mixing iterative and recursive functions just fine. Some people do tend to want to use recursion for everything though, because as a wise man once said "To iterate is human, to recurse is divine."

>>6280 > I've talked to expert programmers who've been at it for 20 years and many of them have said they've never encountered a situation where recursion was desirable. I think a difference should be stated between a recursive program and a recursive algorithm. For example, while quicksort can be implemented in an imperative fashion, the algorithm itself is recursive by nature.

>>6283 Yes, there are certain algorithms which are defined recursively but which can be coded iteratively, sometimes with better results. The Fibonacci sequence is one such creature, and it's described in the CodeProject article above. Coding it recursively is elegant and easily readable by anyone, even those with little to no programming expertise, but it blows the stack fairly quickly.

Here you go OP

>>6293 The `rfib` one has a lot of unnecessary recomputing. To make it worthwhile you should be using memoisation.

>>6148 Can you suggest other programming image boards?

>>6292 >it blows the stack very quickly Only in a language without tail end recursion optimization. Recursion is the much preferred way in languages that do have it (pretty much any functional language).

>>6297 This isn't really the place to ask about other boards. As far as imageboards go, the pickings are pretty slim anyway. >>6302 I think the bulk of this thread should consist of talking about languages that don't have tail recursion optimization (which include some very common languages) and how best to make them behave when used recursively. When you write in a language where tail recursion is a big thing, you're basically just writing iterative code that appears recursive to the reader. It isn't truly recursive, and therefore the thread shouldn't focus on it.

>>6302 >Only in a language without tail end recursion optimization and if you user understands how tail recursion works and makes their code compatible. No amount of compiler magic can save the stack from naive recursion from a developer who doesn't know what they're doing. Assuming developers know what they are doing is a big assumption these days.

>>6306 So then the question becomes whether or not it's ever possible or desirable for a competent developer to use naive recursion. Is there any amount of compiler magic that can make that work?

>>6302 >Recursion is the much preferred way in languages that do have it (pretty much any functional language). This isn't quite true. Plenty of more iterative focused languages have tail recursion as well. It's tail recursion+register pinning that only functional languages usually do and which allows the recursive code to be compiled to exactly the same assembly as an iterative solution. >>6303 >When you write in a language where tail recursion is a big thing, you're basically just writing iterative code that appears recursive to the reader. This is a bit of a misrepresentation of what compilation is. I could as easily say that when you write iterative solutions you're just writing recursive code that looks iterative to you or that all recursive code, regardless of tail optimisation is iterative because it's just stack manipulations really. The code is neither "really" one or the other. They are both simply different ways of looking at the same thing. >>6315 Sure, though it's not so much a compiler thing as knowing when to use it. There are a lot of algorithms that when converted from recursive to iterative need to have a stack added and so don't show meaningful efficiency differences. The problem is when you're using normal recursion to do something that can be achieved by simple iteration. For instance, parsing an infix notation expression (e.g. "5 * (7 + 3) * 2") can be done with Dijkstra's Shunting Yard (an iterative algorithm) or with a few different recursive algorithms and they give comparable speed.

>>6316 >There are a lot of algorithms that when converted from recursive to iterative need to have a stack added and so don't show meaningful efficiency differences. The problem is when you're using normal recursion to do something that can be achieved by simple iteration. Surely there are some situations where simple iteration and simple recursion are both viable, or even where simple recursion wins over simple iteration. I wish there was a ready-made classification system or guide to determine which type of recursion is best suited to a given coding task, if any, because from my experience it's largely down to programming intuition whether to use recursion or not. You could organize problems by where they fall in terms of space or time complexity or both, have a table of problems that people can compare their task to, and have code templates for each scenario. It'd be like a GameFAQ for recursive coding. You don't always need a complete guide to the game. Sometimes you just want to see a listing describing the enemies or weapons. Writing an exhaustive guide that includes appropriate coding strategies for code in general would just be writing a programming book, or more realistically an entire library of programming books, but if it were just for recursion, it might be doable because it generally isn't used as often as iteration. That may be able to answer both the question posed in the OP and a whole load of other questions. Even that might end up being too much to fit neatly in a bite-sized guide, though, but like you said, it's about having a sense of when to use it, and anything that could help people develop that sense even a little would be a major improvement.

>>6351 This should answer the question in the OP.

Can someone explain hyperfunctions to me ?

>>6369 I've read through this paper once but It's a hardo. I'd love a fresh perspective. https://arxiv.org/pdf/1309.5135.pdf

>>6325 Read an intro to algorithms book. I recommend intro to algorithms by Udi Manber. Recursion is literally everywhere in programming. Every time you see a for loop, it is a case of recursion. Let me explain. If you read an intro to alg book, you will realize that 99% of algorithms can be solved by simplifying the problem into one or more simpler cases. Converting a problem into simpler versions of the same problem is the basis for recursion. Let me give an example: summation of an array. sum(vec) = vec[1] + sum(vec[2:end]) I converted summation of an array of length n to a summation of an array of length n-1. This is clearly recursion. But you can write this using a for loop in a straightforward manner since I am calling sum only once. In fact, pretty much all for loops can be understood as being based on recursion. Another example: sorting an array. sort(vec) = merge_sorted_arrays(sort(vec[1:n/2]), sort(vec[n/2+1:end])) I simplified the sorting of a length n array problem into two problems of sorting two length n/2 arrays. Again, recursion. This is slightly harder to convert into a for loop but it's possible with an addition stack datastructure. Point being, pretty much all algorithms use the principle of recursion. For you math nerds, recursion is actually very closed related to induction since you can prove recursive algorithms to be correct using induction. tldr: Study intro to algorithms book and you won't be pattern matching code like that and being so lost in code

>For you math nerds, recursion is actually very closed related to induction since you can prove recursive algorithms to be correct using induction. It's even closer than that, as they are essentially the same. Recursion means describing something in terms of base cases and descriptions of "bigger" things using "smaller" things. To construct something from a recursive definition, you start at the base cases and work your way "up" until you're done. Induction means proving something holds by first proving base cases and then showing that the property can be proven for "bigger" cases when assuming "smaller" cases. To get a proof that the property holds for a certain case, we use the base cases and inductive steps to work our way "up" until we arrive at a proof for the case we are interested in. Here "smaller" can mean smaller numbers, shorter lists or smaller according to your favorite relation (as long as it is terminating). The only difference is that recursion is for objects or values, while induction is for proofs. Accordingly, when using a type theory to describe a logic through the Curry-Howard isomorphism, recursion in the type theory will often correspond to induction in the logic. (This is how it is in Coq for example).

>>6431 This is a very helpful post. Any good recursive programming resources are welcome. If recursion is as prevalent as you say it is, though, why don't more programming classes teach it that way?

>>6441 Because the current state of cs education is so bad I cannot even put it into words. I have taken algorithms class (and other cs classes) in both a >200 ranked university and a top 50 university. There is an enormous gulf between the quality of teaching between the two institutions. In a top 50 (or so) university, you will take an intro to algorithms course with the udi manber book and the clrs book (I use this book to reference algorithms and the udi manber book to learn algorithms) or a similar quality book in your 3rd or 4th year. In that course, you learn how to design and analyse algorithms, using induction and other techniques. And once you learn it, you should be able to understand when to use recursion etc. You don't write a line of code in this class; you only write pseudocode. Unfortunately, in the lower ranked university the intro to algo class teaches you how to code in C/C++, write for loops etc, and write business logic for a department store or whatever as homework. There is such a huge disparity in quality because CS still doesn't have a standard, widespread curriculum. So profs end up teaching what they know, which depends on their background etc. Not to discourage you, since there is lots of good material on the internet. I think you should try to do this intro to algorithms course offered at mit. The lectures are available http://www.youtube.com/watch?v=JPyuH4qXLZ0&list=PL8B24C31197EC371C And problem sets too https://github.com/wangjohn/mit-courses/tree/master/6.046/ You should get good at algo if you take lecture notes and do the problems yourself (with textbooks ofc) . It is hard but I believe it is worthwhile.

>>6444 I've noticed something similar with chemistry curricula between various institutions. Math and physics seem to be the only subjects with any kind of standardization. At any rate, I'm trying to kitbash together a recursively coded elementary cellular automaton, because the answer given in >>6351 is theoretical and sample code is needed. C doesn't allow you to declare arrays within arrays, which would make it a whole lot easier, so I've defined a value based on the CA neighborhood in the 1D array and passed it to a 2D array which is used in a recursive function to generate the complete automaton. Right now I can't decide whether to set the rule to Rule 30 or Rule 90, but that's more of a discussion for the CA thread.

>>6445 You might want to program in a proper language instead of C, which is 1 step away from assembly code. C/C++ programming slowed down my progess a lot when I started learning. I recommend julia but other decent languages for creating matrices or arrays of arrays or lists of lists are python, matlab/octave, ocaml/f#, even haskell. Really any language with a decent REPL.

>>6445 If you need multidimensional arrays and speed is important then the scientific community tends to use Fortran or NumPy.

>>6446 I'm using C because I used to program in C++. I've also never found any examples of recursively coded CAs, so it doesn't matter what language I use because there's nothing to go on anyway. It's been a long time since I tried to do anything serious with it, though. Should I just go ahead and post what I have so far? It's kind of a hot mess right now. It's not even at a stage where it'll compile. It's currently attempting to run Rule 90. I'd like it to accept user-defined values into a 1D array, calculate values for a new row of the 2D array based on that, pass the new row's values back to the 1D array and ultimately print the final 2D array after all steps are complete. >>6451 I may end up doing something with those, but for now I want to go with something more familiar to me.

>>6452 I decided to try to rework this into 2 1D arrays to reduce complexity and it looks like I've almost gotten it to compile, but there's a stubborn syntax error. It's giving me "syntax error before ']' token" on the line when I set up the recursive call during the declaration of my recursive CA function, and then again when the function is actually called in the program, so I'm assuming if I fix one I'll have fixed both. Since the recursive function uses arrays, it has to have something to do with that. This is after having figured out how pointers work with much difficulty, since I was never enough of a programmer to make use of them back when I did C++. This would have been much easier if somebody would have just said "If you have a function that gets passed a sequence of values from an array, when you declare your function you need to specify which value of the array you want it to start at, and when you do it's called a pointer because it's pointing to a specific value and you can't call an entire array into your function at once." Too bad all these damn tutorials on the internet explain pointers in what must be the least intuitive way possible. I see what >>6444 meant about CS education being in the crapper. All these people who wrote these tutorials must have gone to the schools that can't teach CS. I kept the version of the program with the 2D array to compare it, and I've gotten it down to the same syntax error, albeit with more instances of it because a 2D array needs 2 sets of brackets. I don't know what to do with this syntax error because again, the tutorials on the internet aren't being very helpful. I hope this is the last thing I have to deal with before it compiles. Then I can see if it actually does what it's supposed to do and probably get pissed off when instead of generating Rule 90 it writes the Navy SEAL copypasta.

>recursive programming What do you mean by this? Do you mean functions that look like typical mathematical induction transcribed into code, or just any old function that calls itself? e.g. in the following, is acc2 as representative of "recursive programming" as acc1 even though it's completely iterative and could be done as well with a loop?: (define (acc1 ls val) (if (null? ls) val (+ (car ls) (acc1 (cdr ls) val)))) (define (acc2 ls val) (if (null? ls) val (acc2 (cdr ls) (+ val (car ls)))))

>>6445 Store your matrix as a row or column-major array. That's typically how this problem is handled in C. Indexing is i*width + j or whatever. Check this out: https://en.m.wikipedia.org/wiki/Hashlife This is also a good thing to know about if you don't already: https://en.m.wikipedia.org/wiki/Basic_Linear_Algebra_Subprograms

>>6467 It is kind of painful to watch someone do array based programming in C. BLAS shouldn't really be used directly for programming stuff like this...you really should be using some high level library that contains a proper array data structure such as Eigen3 in C++. Or just plain Fortran or Julia. Or Matlab, R, or numpy if you don't want speed. But wasting time doing memory allocations, tracking allocations and freeing in C is kind of sad to see.

>>6466 >or just any old function that calls itself This. >>6468 >It is kind of painful to watch someone do array based programming in C. Well, we can agree on that much. You know what, I'll just go ahead and post what I've got. Maybe someone can tell me where I'm going wrong. inb4 "your first mistake was using C." My code is commented a bit obsessively for people who may not know much about CAs. //This program is written to run the Rule 90 elementary cellular automaton recursively. //Begin program. #include <stdio.h> int c = 0; int d = 0; int i = 0; int n = 0; int x = 0; int y = 0; //x is the length of the 1D arrays that make up the CA. //y is the number of iterations of the CA. //n is the number of the entry in the 1D CA. //i represents the neighborhood of each cell in the CA. //c is a stand-in for i to stop an lvalue error in the CA update rule. It'll equal i mod 2. //d is there for the same reason as c and for formatting purposes. It'll equal n mod x. int main () { //Begin setup. printf("\nEnter number of columns: \n"); scanf("%d", &x); //User defines the number of cells in the 1D CA. printf("\nEnter number of iterations: \n"); scanf("%d", &y); //User defines the number of times the CA will update. int RecursiveECAInput[x]; //Declares the 1D CA array now that its length is known. int RecursiveECAOutput[x]; //Declares the 1D array that temporarily stores iterations of the CA. for(n=0;n<x;n++) //This loop defines the 1D CA's initial conditions. { printf("\nEnter initial value (0 or 1) for Cell %i\n", n); scanf("%d", &RecursiveECAInput[n]); if (RecursiveECAInput[n] != 0 && RecursiveECAInput[n] != 1) //This discards non-binary input. printf("\nUnusable value entered. Enter 0 or 1.\n"); n--; } //End setup. //Begin CA algorithm. The function RecursiveECA90 is declared and then called to perform the algo. n = 0; c = i % 2; d = n % x; void RecursiveECA90(int RecursiveECAInput[n], int RecursiveECAOutput[n], int n, int i, int c, int d) { if (n = 0) RecursiveECAInput[n-1] = RecursiveECAInput[x-1]; //These 2 lines handle edges. if (n = x - 1) RecursiveECAInput[n+1] = RecursiveECAInput[0]; //These 2 lines handle edges. if (n = x * y) return; i = RecursiveECAInput[n-1] + 2*RecursiveECAInput[n] + 3*RecursiveECAInput[n+1]; if (c = 0) RecursiveECAOutput[n] = 0; //These 2 lines are the CA's general update rule. else RecursiveECAOutput[n] = 1; //These 2 lines are the CA's general update rule. printf("\n", RecursiveECAOutput[n]); //This prints the CA's output. if (d = 0) n = 0; //This resets the value of n for the next iteration. if (d = 0) printf("\n"); //This creates a new line when an iteration is done. if (d != 0) return RecursiveECA90(RecursiveECAInput[], RecursiveECAOutput[], n+1, i, c, d); //SYNTAX ERROR HERE } RecursiveECA90(RecursiveECAInput[], RecursiveECAOutput[], n, i, c, d); //I AM ERROR //End CA algorithm. return 0; } //End program.

>>6472 Probably should have italicized most of those comments. It's not terribly readable like that.

>>6472 > RecursiveECAInput[] > RecursiveECAOutput[] You need to put an integer inside those brackets.

>>6472 2 things,: you can't pass arrays as arrays in C, you need to pass them as int * (i.e. everywhere you wrote RecursiveECAInput(int RecursiveECAInput[], .... ) you need instead to write RecursiveECAInput(int *RecuresiveECAInput,....) if you want to test for equality in C you need to write ==. The reason this doesn't give you a compile error is that in C "a = b" is a statement with the value of the assignment, i.e. here b

>>6472 >int RecursiveECAInput[x]; Oh nvm my previous statement. You're using dynamically stack allocated arrays, which is not ANSI C, and I don't remember how to use those.

>>6477 I am >>6475 and >>6477 btw

>>6472 I'm this poster, and I just had a nap. When I woke up, I had what I think is an important thought. There doesn't seem to be anything in RecursiveECA90 that passes values back from RecursiveECAOutput to RecursiveECAInput. Therefore there's no way for the values in Input to update, and what'll happen is that when I get the program to compile, it'll just print the first line and then print the second line over and over again because it's still operating on the first set of input data. I need to add a line or two that fixes this. >>6475 >>6477 Yeah, it's set up that way in order to let the user decide the size of the 1D CA. >>6476 >you can't pass arrays as arrays in C, you need to pass them as int * (i.e. everywhere you wrote RecursiveECAInput(int RecursiveECAInput[], .... ) you need instead to write RecursiveECAInput(int *RecuresiveECAInput,....) Is this the source of the "syntax error before ']' token" stuff? >if you want to test for equality in C you need to write ==. The reason this doesn't give you a compile error is that in C "a = b" is a statement with the value of the assignment, i.e. here b Yeah, I forgot about this. Fortunately it's easily remedied.

>>6483 Actually, come to think of it I don't even think it'll print the first line, but all I need to fix that is a printf command for RecursiveECAInput just before RecursiveECA90.

>>6484 *printf loop. Ah programming, you have so many ways to screw up. I'm more into physics and chemistry than programming, but every so often I need to write a program to do something scientific, and every single time I end up needing many attempts before it works properly. Programming is a delicate, intricate art that requires creativity and tenacity, and I have a great deal of respect for people who choose it as a profession.

>>6468 >It is kind of painful to watch someone do array based programming in C. double *array = malloc(height*width*sizeof(double)); access element i,j with array[i*width+j]; or to avoid having to pass dimensions around: struct Matrix { int height; int width; double elements[]; }; struct Matrix *M = malloc(height*width*sizeof(double)+sizeof(struct Matrix)); if you really don't want to think about it, do something like this... double *get_element(struct Matrix *M, int i, int j) { return M->elements[i*M->width+j]; } ...or put that in a macro if you're worried about it getting inlined. what's so hard about that? >BLAS shouldn't really be used directly for programming stuff like this why? it's always worked fine for me. >But wasting time doing memory allocations, tracking allocations and freeing in C is kind of sad to see. memory management kind of comes with the territory. look, i use both julia and python all the time for this stuff, but i've also never had a problem doing scientific programming in C.

>>6486 Yeah I use arrays exactly like that in C and I know how to use it in C. It's not to difficult for me either but working with julia or python is clearly miles better and much less error prone. I've worked with straight blas too but again it is much less error prone to work with a proper matrix library like eigen. Most importantly though, for someone who is literally still allocating his arrays on the stack, he should start with python or julia instead. Recommending that he start with C simply delays his progress by a significant amount of time.

>>6485 >Programming in C/C++/ASM is a delicate, intricate art that requires creativity and tenacity Fixed

>>6483 yep

>>6496 Yep to which part of that?

>>6511 sorry, what i meant is that it is indeed the source of the syntax error.

>>6489 Ah I see where you're coming from. I was just being defensive because I like doing this kind of work in C sometimes. I will say there is value in handling the arrays directly if that anon is doing this for learning purposes. I recently did something very similar in Julia, and optimizing it would have been tough if I didn't have any intuition about what was going on behind the scenes.

Well, I finally got the program to compile and run, and also put better measures in place to sanitize input, but it still doesn't work like it's supposed to. It'll accept all the requested values correctly and print them as the first iteration of RecursiveECAInput, but that's all it does. The rest of the CA doesn't display or possibly even run. For some reason, when I remove the brackets from RecursiveECAInput/Output at the point where they're called in RecursiveECA90 and thereafter, that gets rid of the compilation errors even though they're arrays and should be called with brackets (or an asterisk). I don't know what's going on with that. I found that if I add a line setting n to a certain value immediately before RecursiveECA90, it seems as though a second iteration is attempting to print with strings of 0s and 1s of variable length and content depending on what n is set to, but if I erase that line the second iteration is just a single 1 or 0 depending on the input. So it seems like it's attempting to run the second and succeeding iterations, but something is stopping it. Also, when I get this working I'd like to figure out a better way to display the output than 1s and 0s in text form, like an actual grid, and maybe add a loop that allows you to start again with another set of input without having to exit the program and reopen it. Here's what I currently have, this time with better italics: //This program is written to run the Rule 90 elementary cellular automaton recursively. //Begin program. #include <stdio.h> int c = 0; unsigned int d = 0; int n = 0; int i = 0; int x = 0; int y = 0; //x is the length of the 1D arrays that make up the CA. //y is the number of iterations of the CA. //n is the number of the entry in the 1D CA. //i represents the neighborhood of each cell in the CA. //c is there to sanitize the number of columns and iterations. //d is to keep the program running at the end so you can look at your output until you exit. int main () { //Begin setup. for (c=0;c<=0;c++) { printf("\nEnter number of columns: \n"); scanf("%d", &x); //User defines the number of cells in the 1D CA. printf("\nEnter number of iterations: \n"); scanf("%d", &y); //User defines the number of times the CA will update. if (x == 0) printf("\nUnusable number of columns entered. Enter a positive integer.\n"); if (x == 0) c--; if (x < 0) printf("\nUnusable number of columns entered. Enter a positive integer.\n"); if (x < 0) c--; if (y == 0)printf("\nUnusable number of iterations entered. Enter a positive integer.\n"); if (y == 0) c--; if (y < 0)printf("\nUnusable number of iterations entered. Enter a positive integer.\n"); if (y < 0) c--; } int RecursiveECAInput[x]; //Declares the 1D CA array now that its length is known. int RecursiveECAOutput[x]; //Declares the 1D array that temporarily stores iterations of the CA. for(n=0;n<=x-1;n++) //This loop defines the 1D CA's initial conditions. { printf("\nEnter initial value (0 or 1) for Cell %i\n", n); scanf("%d", &RecursiveECAInput[n]); if (RecursiveECAInput[n] != 0 && RecursiveECAInput[n] != 1) //This discards non-binary input. printf("\nUnusable value entered. Enter 0 or 1.\n"); if (RecursiveECAInput[n] != 0 && RecursiveECAInput[n] != 1) n--; } for(n=0;n<x;n++) //This prints the input data as the first iteration of the CA. { printf("%d", RecursiveECAInput[n]); } //End setup. //The program fails at this point. Adding the line with n equal to some value here creates the appearance that the program is trying to do something, but whatever it is, it's not what was intended. //Begin CA algorithm. The function RecursiveECA90 is declared and then called to perform the algo. printf("\n"); void RecursiveECA90(int RecursiveECAInput[n], int RecursiveECAOutput[n], int n, int i) { if (n == 0) RecursiveECAInput[n-1] = RecursiveECAInput[x-1]; //These 2 lines handle edges. if (n == x - 1) RecursiveECAInput[n+1] = RecursiveECAInput[0]; //These 2 lines handle edges. i = RecursiveECAInput[n-1] + 2*RecursiveECAInput[n] + 3*RecursiveECAInput[n+1]; if (i % 2 == 0) RecursiveECAOutput[n] = 0; //These 2 lines are the CA's general update rule. else RecursiveECAOutput[n] = 1; //These 2 lines are the CA's general update rule. printf("%d", RecursiveECAOutput[n]); //This prints the CA's output. if (n % x == 0) n = 0; //This resets the value of n for the next cycle. if (n % x == 0) printf("\n"); //This creates a new line when a cycle is done. if (n % x == 0) RecursiveECAInput = RecursiveECAOutput; //This updates the input array. if (n == x * y) return; if (n % x != 0) return RecursiveECA90(RecursiveECAInput, RecursiveECAOutput, n+1, i); } RecursiveECA90(RecursiveECAInput, RecursiveECAOutput, n, i); //End CA algorithm. { while (1 == 1) d++; //This keeps the program up until you close it. } return 0; } //End program.

>>6555 >array Clever girl.

>>6555 Do you know about gdb? You can use it to debug your c code, meaning you can step through your program step by step and check values of variables at each step. Doing this will help you understand what's happening during execution and where your bugs are.

>>6559 Never heard of it before. Seems like something worth looking into. Anything more specific to add?

>>6524 Yeah I guess we all have to go through those steps learning C

>>6555 I'm gonna go out on a limb and guess that you're a maths person without much coding experience. I don't really understand what your CA is supposed to do but I think your logic is mostly sound. Your syntax is absolutely bonkers, like I'm genuinely surprised you convinced it to compile. My C fu isn't that strong and I honestly didn't know you could define a function within a function like that. There are a lot of problems with the code but most of it is stupid gotchas. That's a good sign because it means you're not making fundamental misunderstanding mistakes. The things I noticed are: When handling edges it writes the correct value into the input array and then keeps right on going calculating i (from random memory over the edge of the array) and setting the cell again based on it. Also, the assignment statements on those lines assign beyond the bounds of the array. So, n==0 gives us an index of n-1 which is -1. Likewise n==x-1 gives us n+1 which is x i.e. the length of the array, one beyond it's largest valid index. Also note that it's setting values in the input array there rather than the output. I'm not sure if that's intended. "This updates the input array." Not quite, it replaces the local input array pointer with the output pointer. So, when it comes to make the next recursive call (and for all recursive calls down from that) both the input and output are the same array (the original output array) and our original input array is inaccessible. Note that local variables don't affect things outside their function, so once we get back to the main function the input pointer is back to it's original value (technically it never changed, a copy of it was made when the call happened). If you #include <strings.h> you get a function called memcpy. memcpy(RecursiveECAInput, RecursiveECAOutput, n*sizeof(int)); will get you what you want for that line. You forget to reset n between using it to print the input data and passing it to the recursive function. On the first function call n==x, which is why it doesn't do much. There's also a lot of syntax stuff. Most importantly you can use {} after an if in order to have multiple statements that depend on it. You can put them inside of each other as well. if(x==0) printf("hi"); if(x==0) c--; //is equivalent to if(x==0){ printf("hi"); c--; } Also you can just declare local variables that only exist within a function (arguments are an implicit form of local variable). For instance the i argument to your call can be removed and "i=blah;" replaced with "int i=blah;" for the same effect. >>6559 I wouldn't worry about gdb for now. It can be quite technical. Probably better to stick to liberal use of print statements during debugging. If you're going to be doing a lot of code it's something to learn though.

>>6555 https://stackoverflow.com/questions/6567742/passing-an-array-as-an-argument-to-a-function-in-c

>>6563 >When handling edges it writes the correct value into the input array and then keeps right on going calculating i (from random memory over the edge of the array) and setting the cell again based on it. Also, the assignment statements on those lines assign beyond the bounds of the array. So, n==0 gives us an index of n-1 which is -1. Likewise n==x-1 gives us n+1 which is x i.e. the length of the array, one beyond it's largest valid index. The idea here was for the edge handling to wrap around. A cellular automaton operates on a neighborhood, which is a group of cells that some mathematical operation is performed on to decide which state the cell will be in for the next iteration. If that cell is on the edge, the full neighborhood can't be calculated because one or more of the cells is missing, unless some sort of exception is made. In this case the exception is intended to be treating the last cell in the line like the cell before the first one, and treating the first cell in the line like the one after the last one. >Also note that it's setting values in the input array there rather than the output. I'm not sure if that's intended. Both the input and the output array have to update, as each new line is calculated based on the input from the previous line. It needs to calculate the output, print that and then write the values of the output array to the input so the next round can be performed. >You forget to reset n between using it to print the input data and passing it to the recursive function. On the first function call n==x, which is why it doesn't do much. I had a line that set n = 0 before, but I deleted it because I couldn't tell why the recursive function didn't want to print any more arrays beyond the first one, or why it would print more than one digit if I changed the value of n. I guess I should put it back. >If you #include <strings.h> you get a function called memcpy. memcpy(RecursiveECAInput, RecursiveECAOutput, n*sizeof(int)); will get you what you want for that line. Is that the only way to do this? >Most importantly you can use {} after an if in order to have multiple statements that depend on it. This will make it look much neater. Also, from the tutorials I've been reading, setting int *(arrayname) is the same as int arrayname[]. The main thing I don't get is why taking the brackets away in the recursive function got rid of the compilation errors. Is it even still registering that an array is supposed to be called there? When I run my printf loop to get values for the array, the bracket syntax works just fine, but for some reason I can write it the same way in the recursive function and it doesn't work.

>>6568 I just tried adding n = 0 back and breaking this line: printf("%d", RecursiveECAOutput[n]); by changing it to printf(RecursiveECAOutput[n]); just to see if the recursive function is actually doing anything. With the former, the program printed another line with a single 1 after my input array, whereas with the latter it didn't print a second line and then crashed. This seems like an important clue so I thought I'd post it. It proves that the function is doing something, although obviously not the right thing.

>>6568 >The idea here was for the edge handling to wrap around Ah, I see. You can't wrap like that in C. Some languages will do it but C doesn't keep track of how big your arrays are and so if you try to go past the bounds it just happily does so and starts accessing memory that doesn't belong to the array. If you want the first or last element you'll have to use 0 and x-1. >Both the input and the output array have to update Ahh right I see. So both modifying the input and continuing on to calculate i on the edges was intended. The problem is that you can't safely go past the end of your arrays like that. So, in this case, with most compilers, output[-1] happens to be the same memory as input[x-1] because the two arrays will probably be placed next to each other in memory. Different compilers/optimisation settings/phases of the moon could affect this though. Never ever rely on it. Always stay inside your bounds. >Is that the only way to do this? No, you can also just loop through the array and copy one element at a time. Note that there's no way to just implicitly copy the whole thing because C doesn't know how big it is. If you want to be fancy you can swap the two array pointers instead of copying. I wouldn't bother though. While it's faster for the processor to avoid copying, it adds complexity in having to work out which array was the output array for the last iteration once you're finished. Also, I made a mistake in my memcpy line. It should be "x*sizeof(int)" rather than "n*sizeof(int)". >Also, from the tutorials I've been reading, setting int *(arrayname) is the same as int arrayname[] Yep, both of those indicate that arrayname is a pointer to integers. By convention the first is a pointer to a single integer (i.e. an array of length 1) and the second to a larger array but it's all the same to C as it's not tracking the length anyway. >The main thing I don't get is why taking the brackets away in the recursive function got rid of the compilation errors I'm not quite sure where the brackets were. You shouldn't be putting empty brackets anywhere other than a declaration. If you want the array itself (i.e. the pointer) you just don't put any brackets.

>>6586 >Ah, I see. You can't wrap like that in C. Some languages will do it but C doesn't keep track of how big your arrays are and so if you try to go past the bounds it just happily does so and starts accessing memory that doesn't belong to the array. If you want the first or last element you'll have to use 0 and x-1. So I could have it wrap around as long as I don't do it by referencing something outside the bounds of the array, then. Problem is, I have i defined with (n-1) and (n+1) as components, so how am I supposed to handle that in edge cases? Do I just create another definition of i for those cases? >No, you can also just loop through the array and copy one element at a time. Note that there's no way to just implicitly copy the whole thing because C doesn't know how big it is. I guess that can just be implemented as another for loop. There's actually quite a bit of iterative code in this program so far for what was supposed to be an exercise in recursion. I've read about ways to get and print values recursively, so I suppose there's a way to copy arrays recursively as well. Should I really make a big deal out of making every aspect of this program recursive? Recursion is supposed to be one of those things that you only use in special cases, according to most programmers. >I'm not quite sure where the brackets were. You shouldn't be putting empty brackets anywhere other than a declaration. If you want the array itself (i.e. the pointer) you just don't put any brackets. See >>6472 for the previous locations of the brackets in the array calls. Some of the things I've read indicate that you can just set Array1 = Array2 and that'll copy one array to the other, which is what I tried to do. Apparently it doesn't work that way.

>>6587 >Do I just create another definition of i for those cases? Ayup. >so I suppose there's a way to copy arrays recursively as well Every iterative algorithm has a recursive equivalent and vice versa. >Should I really make a big deal out of making every aspect of this program recursive? I wouldn't bother. Some programming styles prefer recursion for simple things like this but C was not made for those styles. >See >>6472 for the previous locations of the brackets in the array calls Ahh right yeah. You don't want those brackets there. Empty brackets like that are only used in definitions to say that the type of the variable is an array. Once it's defined you just use the name bare. >Apparently it doesn't work that way. Yeah, it just copies the pointer.

>>6595 >Ayup. All right then. This edge handling is probably why it won't print a second iteration. Going to revise that. Of course, I'll also have to correct the updating mechanism to actually get it to evaluate and print the whole CA. >Every iterative algorithm has a recursive equivalent and vice versa. So I've heard. >Some programming styles prefer recursion for simple things like this but C was not made for those styles. There's a discussion in the CA thread about the possibility of using recursion to code one. The specifics of why I ended up going with Rule 90 are mentioned. The idea was that the best candidate CAs to be coded recursively are those that generate recursive structures, because that's the only time you can actually gain computational efficiency from using recursion. CA Rule 90 is sometimes called the Sierpinski automaton because not only can it generate Sierpinski triangles, every pattern it generates is a superposition of Sierpinski triangles. Even the most random-seeming arrangements of triangles you can make with it, such as the one at the top of the Wikipedia article (pic related, it's that picture), are just combinations of Sierpinski triangles superposed onto each other. The Sierpinski triangle is probably the archetypal example of a recursive structure, so a CA that generates nothing but that seems like the best choice. I did spend some time trying to figure out ways to make Rule 30 work recursively, but Rule 30 doesn't have those traits as it produces nothing but randomness no matter which input is entered, so it's a poor choice for this. Theoretically Rule 30 will produce some repeating structures eventually, but it takes a long time and given that Rule 30 was employed as an RNG, repeating structures aren't a good idea there. Not only that, I found Rule 90 easier to code in general than Rule 30. I suppose if I was writing this in one of those other languages besides C, maybe one where you can wrap an array around, the whole program would be recursively written, but I just did what seemed convenient with the exception of the CA algorithm itself. The idea was to gain efficiency by only using recursion in areas where it's warranted, meaning only the CA algorithm. I doubt recursively gathering values for an array would be more efficient. >Ahh right yeah. You don't want those brackets there. Empty brackets like that are only used in definitions to say that the type of the variable is an array. Once it's defined you just use the name bare. That seems somewhat counterintuitive. You'd think arrays should be given some sort of distinction, but if I can just type the name of the array, that's less work. >Yeah, it just copies the pointer. Internet tutorials lied to me again.

>>6602 Well, I just changed the definition of i to this: if (n == 0) i = RecursiveECAInput[x-1] + 2*RecursiveECAInput[n] + 3*RecursiveECAInput[n+1]; else if (n == x - 1) i = RecursiveECAInput[n-1] + 2*RecursiveECAInput[n] + 3*RecursiveECAInput[0]; else i = RecursiveECAInput[n-1] + 2*RecursiveECAInput[n] + 3*RecursiveECAInput[n+1]; Now there shouldn't be any out-of-bounds array calls in the function, and I made two more important changes. First, I realized that I plumb forgot to tell the function to call itself recursively if n mod x = 0. Seeing as n starts out equaling 0 and the printf statement is right before that if statement, it won't get to the part where it calls itself, so that explains why the printf command only printed one digit. I added a recursive call to that if statement and it now prints iterations correctly. Second, I changed RecursiveECAInput = RecursiveECAOutput to a for loop as suggested by >>6586, and the arrays appear to be updating properly now, marking a major step towards completion. Unfortunately I now have an equally major problem. Whereas before the program would only print one digit, now it prints an endless amount of iterations until the program crashes. I suspect that's because of this line: if (n == x * y) return; This conflicts with the commands for the instances where n mod x = 0, because when n = x * y, n mod x will also equal 0. I tried adding an && exception to the if n mod x statement for when n = x * y, but it didn't work. I'm not sure how to rectify this. Obviously I need it to know when to stop. On the subject of whether what I have shows any semblance of working as intended, as the iterations scroll down the screen, I can almost make out triangular patterns in it. I think the wraparound idea for the edge handling may not have been the best, because the triangle patterns are now scrolling across the screen instead of generating a Sierpinski triangle. Rule 90 isn't supposed to generate random output with simple input, which is what I tried on it, but when the edge handling is in a wraparound style, the patterns will interfere with each other. I may need a different sort of edge handling. At least it's actually doing something now though.

>>6602 >R090_rand_0.png >46.82 KB, 500x500 This image is compressed over 5 to 1, so it's quite far from random. Just sayin'.

>>6608 I'm currently messing around with the program to see what it does so I can figure out what's wrong with it, and I discovered that if I tell it to do only 1 iteration, it does it without printing them endlessly, but if I enter any number of iterations higher than 1 I get an endless loop. Huh.

Holy heck, please stop using 1 character variable names!

>>6611 What's wrong with 1 character variable names? What makes them any worse than other variable names? Are they just not descriptive enough? Anyway, it makes sense that it would stop after 1 iteration when told to because it's told to stop when n = x * y and when y is set to 1, it stops when n = x, and x is the number of values in the array, meaning it'll print one full cycle. But if it's doing that, why does it keep going endlessly when y is anything else? Geez.

>>6555 here you go lain. seems like you need an example. see attached (ignore the ".txt"). keep in mind that my solution is deliberately naive, for the sake of being straightforward and idiomatic. also, i didn't do it recursively because IMO it's the wrong approach for this problem. some comments: - you need to figure out how to use pointers right. stack-allocating arrays is not how you do this. it doesn't work like matlab. - your global variables shouldn't be global. put them in main. - you can't define functions in other functions (main is a function). put them before main in the file. - break your code out into utility functions, for god's sake. look at what i did for (i hope) a good example. - just because i wouldn't use recursion doesn't mean you can't, but your recursion is very clumsy. practice with something else first. in school, they will typically have you start with various sorting algorithms, so you might want to do that. - the user input handling is really basic. it would be better to load the initial state from a file, or at least a space-separated list, but that part doesn't really matter at this stage. example output for width=80 with one active initial cell (in the middle) * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

>>6613 fuarrrk... tfw can't triforce

>>6555 also, check this out /* Elementary CA rule * r: rule number * c: neighborhood */ static unsigned char rule(unsigned char r, unsigned char c) { return (r >> (c&0x07))&0x01; } now you can run simulations for any rule without changing your code.

>>6613 >here you go lain. seems like you need an example. see attached (ignore the ".txt"). keep in mind that my solution is deliberately naive, for the sake of being straightforward and idiomatic. also, i didn't do it recursively because IMO it's the wrong approach for this problem. Well, we do need an example of it being done iteratively to compare against, and we'll need similar examples for any recursion project anyone in the thread brings up. One of the reasons I went for the recursive approach is to have to deal with less code, and your code is almost twice as many lines as mine. Is there some program you can run your code through to find out where it falls in terms of big-O complexity? >you can't define functions in other functions (main is a function). put them before main in the file. I just moved my RecursiveECA90 declaration to before int main (). >your global variables shouldn't be global. put them in main. I can't declare RecursiveECA90 before main unless I put them before main as well. Of course I could just declare the arrays with malloc instead, thus allowing me to declare things differently, but I'm going for the naive, simple approach. Is there anything particularly bad about global variables? >just because i wouldn't use recursion doesn't mean you can't, but your recursion is very clumsy. As I said before, I can't find any examples of recursively coded CAs to base my estimation of clumsiness or elegance on. If you know of one, I'd like to take a look at it. >the user input handling is really basic. it would be better to load the initial state from a file, or at least a space-separated list, but that part doesn't really matter at this stage. I was thinking about ways of doing this, since different applications of CAs might require various methods of obtaining input. I've also been thinking about ways to make the output look neater, but I'll cross that bridge when I get to it. On another note, there are applications for which an endless stream of output is desirable, so I guess the state it's in right now isn't completely useless. If you were to attempt to run a machine of some sort on a CA, you wouldn't want it to terminate until you turn the machine off. >>6614 I'm getting a similar error where my output prints the first digit of the second iteration on a separate line from the rest of it. I don't know why it would do that. I guess neither one of us can triforce.

>>6620 Last thing before I take off for tonight: I just tested it with all 0s and all 1s for input, and the output should be uniform with no variation if I do that, but it's not. Looks like my calculation rule needs revision as well. I'd prefer to have a more efficient method of doing it than checking 8 different cases, but I may end up having to.

>>6620 >Is there some program you can run your code through to find out where it falls in terms of big-O complexity? no idea. better programmers than me can usually figure it out by just reading through the algorithm. but there are much lower-hanging fruits here, if you just want it to be fast. unrolling the convolution into a matrix-vector product and using a linear algebra library will speed it up quite a bit. this even works in the 2D case. you also might consider dealing with cells stored as bits rather than ints or even bytes (like in my example). >I can't declare RecursiveECA90 before main unless I put them before main as well. You should pass the indices (or pointers) as variables. Don't use the global scope for your loop indices. >Is there anything particularly bad about global variables? Well for one thing, it means that your algorithm isn't actually recursive. Recursive algorithms rely on an internal halting condition which depends only on their arguments. Look at how it's done with this bubblesort implementation (I didn't write this, I just found it). // A function to implement bubble sort void bubbleSort(int arr[], int n) { // Base case if (n == 1) return; // One pass of bubble sort. After // this pass, the largest element // is moved (or bubbled) to end. for (int i=0; i<n-1; i++) if (arr[i] > arr[i+1]) swap(arr[i], arr[i+1]); // Largest element is fixed, // recur for remaining array bubbleSort(arr, n-1); } >>6622 >the output should be uniform with no variation if I do that, but it's not You're right. My mod function is wrong. Here's the correction. static int mod(int x, int n) { return (x%n+n)%n; } >I'd prefer to have a more efficient method of doing it than checking 8 different cases, but I may end up having to. see >>6619 . i just did it that way because it's more obvious what's going on. wasn't sure how familiar you were with bit twiddling in C.

>>6627 Hold everything. I had a thought that might be the one thing that makes my attempt to code Rule 90 recursively worth it and solves almost all of its problems at once. Since Rule 90 is made up entirely of different arrangements of Sierpinski triangles, would it be possible to code it by simply telling the program to generate a Sierpinski triangle upon encountering a 1 in the input line and then using some conditional statements to handle when the triangles are superposed over each other? That seems more intuitive and recursive than how it is now. I don't know if it can be done that way, but if it can, I suspect it may be the easiest and most direct method of coding Rule 90. Anyone want to take a crack at answering this?

Well, I fixed the infinite loop problem. I'd been resetting n to 0 too many times, so it just never got to a value where the loop can terminate. It now works almost correctly, but strangely only for small numbers of columns and iterations. Ignoring the fact that the calculation needs revision, if I tell it to do any number of columns or iterations up to 8, it works fine. If I raise the number of either one higher than that, I have to lower the other by a certain amount, or the program terminates prematurely. This makes the least sense of any programming error I've ever seen. I was also going to ask how I can sanitize my input to stop it from accepting letters when I only want to allow numbers, but that's ancillary to the larger point. Making it a Sierpinski machine is looking more tempting every minute. Somehow I doubt most of these errors are even possible with that method.

I just encountered an even dumber problem than the last one. I decided I'd try to pretty up the output a bit, so I changed printf("%d", RecursiveECAOutput[n]); to if (RecursiveECAOutput[n] = 1) printf("*"); else printf(" "); so I could get it to print asterisks in place of the 1s. What I was expecting was getting the same miscalculated barrage of random 1s and 0s that I've been getting, except that all the 0s would be blank spaces and all the 1s would be asterisks. Imagine my surprise when the output is now all asterisks. What the hell is this? Why would telling it to print differently change the results? I'm about to tear my fuarrrking hair out because this is so unbelievably fuarrrking retarded. There is absolutely no reason it should be doing that.

>>6648 Turns out the same thing happens if I change printf("%d", RecursiveECAInput[n]); to a similar if-else statement. My input will now be printed as all asterisks as well.

>>6648 >>6649 equality test: == assignment: =

>>6650 durka durr. That was even mentioned earlier in the thread. I'm just getting so pissed off by these fuarrrking retarded errors it slipped my mind.

I'm going to take a break from this for now before I start smashing things. I'm having a hard time fixing this error where there's an extra entry before or after, or even to one side of what should be a square matrix. I added a conditional to print the last entry because it wasn't doing it before, so I figure any such errors have to do with the value of n. The first value it gives is also on a different line from everything else, so I guessed there was a conflict between two separate if statements where n = 0. I've tried several approaches to remedy this, but it just doesn't want to work. As far as the CA itself goes, now that I've gotten it to generate stable output in at least some cases, I can look at what it's giving me and tell that it's not calculating properly because I can look at 2 different cells where the 3 cells above it are 111, and it'll render 1 in one case and 0 in the other. That's bad enough, but the thing where it won't terminate properly if you have more than a certain number of spaces is just stupid as hell. I've never seen anything like that before and I doubt I ever will again.

>>6627 >return (x%n+n)%n; The first %n is pointless.

>>6654 Your chances of getting help would be greatly improved by attaching the latest and complete source file to your post, after switching to meaningful variable names.

>>6656 I'm a bit hesitant about posting version after version of code. I don't want to spam the whole thread up with it since this is supposed to be for everyone's recursive coding projects. I did change my variable names though. Hopefully the new ones will be easier for others to understand. //This program is written to run the Rule 90 elementary cellular automaton recursively. //Begin program. #include <stdio.h> int InputJanitor = 0; int ArrayCopy = 0; int ArrayEntry = 0; int Hood = 0; int ColumnNum = 0; int IterateNum = 0; int Exit; //ColumnNum is the length of the 1D arrays that make up the CA. //IterateNum is the number of iterations of the CA. //ArrayCopy is for copying the output array to the input array. //ArrayEntry is the number of the entry in the 1D CA. //Hood represents the neighborhood of each cell in the CA. //InputJanitor is there to sanitize the number of columns and iterations. //Exit is to exit the program. void RecursiveECA90(int RecursiveECAInput[ColumnNum], int RecursiveECAOutput[ColumnNum], int ArrayCopy, int ArrayEntry, int Hood) { if (ArrayEntry == ColumnNum * IterateNum) { if (RecursiveECAOutput[ColumnNum-1] == 1) printf("1"); else printf("0"); return; } if (ArrayEntry == 0) Hood = RecursiveECAInput[ColumnNum-1] + 2*RecursiveECAInput[ArrayEntry] + 3*RecursiveECAInput[ArrayEntry+1]; else if (ArrayEntry == ColumnNum - 1) Hood = RecursiveECAInput[ArrayEntry-1] + 2*RecursiveECAInput[ArrayEntry] + 3*RecursiveECAInput[0]; else Hood = RecursiveECAInput[ArrayEntry-1] + 2*RecursiveECAInput[ArrayEntry] + 3*RecursiveECAInput[ArrayEntry+1]; if (Hood % 2 == 0) RecursiveECAOutput[ArrayEntry] = 0; //These 2 lines are the CA's general update rule. else RecursiveECAOutput[ArrayEntry] = 1; if (RecursiveECAOutput[ArrayEntry] == 1) printf("1"); else printf("0"); if (ArrayEntry == 0) { if (RecursiveECAOutput[0] == 1) printf("1"); else printf("0"); ArrayEntry++; } if (ArrayEntry != 0 && ArrayEntry % ColumnNum == 0) { //This creates a new line when a cycle is done. for (ArrayCopy=0;ArrayCopy<ColumnNum;ArrayCopy++) //This updates the input array. { RecursiveECAInput[ArrayCopy] = RecursiveECAOutput[ArrayCopy]; }; ArrayCopy = 0; printf("\n"); ArrayEntry++; return RecursiveECA90(RecursiveECAInput, RecursiveECAOutput, ArrayCopy, ArrayEntry, Hood); } if (ArrayEntry % ColumnNum != 0) return RecursiveECA90(RecursiveECAInput, RecursiveECAOutput, ArrayCopy, ArrayEntry+1, Hood); } int main () { //Begin setup. for (InputJanitor=0;InputJanitor<=0;InputJanitor++) { printf("\nEnter number of columns: "); scanf("%d", &ColumnNum); //User defines the number of cells in the 1D CA. printf("\nEnter number of iterations: "); scanf("%d", &IterateNum); //User defines the number of times the CA will update. if (ColumnNum == 0) { printf("\nUnusable number of columns entered. Enter a positive integer.\n"); InputJanitor--; } if (ColumnNum < 0) { printf("\nUnusable number of columns entered. Enter a positive integer.\n"); InputJanitor--; } if (IterateNum == 0) { printf("\nUnusable number of iterations entered. Enter a positive integer.\n"); InputJanitor--; } if (IterateNum < 0) { printf("\nUnusable number of iterations entered. Enter a positive integer.\n"); InputJanitor--; } } int RecursiveECAInput[ColumnNum]; //Declares the 1D CA array now that its length is known. int RecursiveECAOutput[ColumnNum]; //Declares the 1D array that temporarily stores iterations of the CA. for(ArrayEntry=0;ArrayEntry<=ColumnNum-1;ArrayEntry++) //This loop defines the 1D CA's initial conditions. { printf("\nEnter initial value (0 or 1) for Cell %i\n", ArrayEntry); scanf("%d", &RecursiveECAInput[ArrayEntry]); if (RecursiveECAInput[ArrayEntry] != 0 && RecursiveECAInput[ArrayEntry] != 1) //This discards non-binary input. { printf("\nUnusable value entered. Enter 0 or 1.\n"); ArrayEntry--; } } printf("\n"); for(ArrayEntry=0;ArrayEntry<ColumnNum;ArrayEntry++) //This prints the input data as the first iteration of the CA. { if (RecursiveECAInput[ArrayEntry] == 1) printf("1"); else printf("0"); } //End setup. //Begin CA algorithm. The function RecursiveECA90 is called to perform the algo. ArrayEntry = 0; printf("\n"); RecursiveECA90(RecursiveECAInput, RecursiveECAOutput, ArrayCopy, ArrayEntry, Hood); //End CA algorithm. printf("\nType any character and press Enter to exit."); scanf("%d", &Exit); //This keeps the program up until you close it. return 0; } //End program.

>>6659 Oh fuarrrk me, I forgot to put [/code]. This is why I wanted to take a break from it.

>>6660 Mod help with this plz?

>>6477 https://gcc.gnu.org/onlinedocs/gcc-7.3.0/gcc/Variable-Length.html#Arrays-of-Variable-Length

>>6659 There are a billion things to clean up and a few things that are wrong. ArrayEntry never decreases so it goes outside the array. You are printing every line leader and the very last cell twice. You are entirely skipping the second cell of every line because ArrayEntry is incremented twice. Hood and ArrayCopy are not used before assignment so dump them as parameters and make them local variables. Move your cell printing if block out into a function. Move your array copy loop out into a function. Switch the array function parameters from int [ColumnNum] to int *. Stop returning the result of a void function. Remove utility variables like InputJanitor from globals and make them local to the function that needs them. The root cause of your problems is this design fault: you are mixing the cell update case with the end-of-line case. Mixing the regular case with the exceptional case is precisely what you should never do in a recursive design, because the result is spaghetti. After locals, RecursiveECA90 should be untangled like this: if (ArrayEntry == ColumnNum) { /* end-of-line handling */ ... } else { /* cell update case */ ... } The cell update branch should only do the cell update, display and recursion with +1. The end-of-line branch should check for end of loops, otherwise recurse by resetting ArrayEntry, swapping the in/out array order and increasing the loop counter. You'll need a loop counter parameter and you can dump the array copying entirely. Here's some programming advice since you appear to be fairly new: make a clean design your top priority. The alternative, keeping a faulty design and patching it with an ever increasing number of fixes, is a path into the abyss. Main is also bonkers -- e.g. enter invalid ColumnNum and IterateNum and get asked for two more rounds -- but fix the previous stuff first.

>>6676 Hey, I just came back, but I'm too tired to do anything with this right now. I'll take a look at it tomorrow. I just thought I'd post the output the program is giving right now. Notably, I tried changing the edge handling to where Hood just equals 0 if ArrayEntry is on the edge, but that didn't change the output at all. I'd still like to hear someone's opinion on coding it as a Sierpinski generator, but I think I still want to do this version of it so I'll have something to compare it against.

>>6676 >ArrayEntry never decreases so it goes outside the array. I had a segment that reset ArrayEntry to 0, but it generated an infinite loop. It shouldn't do that because I had it inside an if-else statement which should only be triggered if ArrayEntry is at the end of a line. I think I need a new parameter to measure overall progress through the sequence instead of just through one line, as you mention later on. That's the only way I'll ever get this conflict between different cases of ArrayEntry to resolve. >You are printing every line leader and the very last cell twice. You are entirely skipping the second cell of every line because ArrayEntry is incremented twice. I erased one of the ArrayEntry++ instances, but again, I thought it wouldn't matter because it was inside an if-else statement. I'm not sure what's causing it to do these things, but if I redesign it with the second parameter, hopefully they'll disappear. >Hood and ArrayCopy are not used before assignment so dump them as parameters and make them local variables. >Remove utility variables like InputJanitor from globals and make them local to the function that needs them. People seem to not like global variables in general. Is there ever a time when they're actually useful? >Move your cell printing if block out into a function. Move your array copy loop out into a function. I thought it'd be simpler if I just stuffed all of it into RecursiveECA90, but maybe not. >Switch the array function parameters from int [ColumnNum] to int *. I was told to do this earlier, but the tutorials I read said it was the same thing, and I tried it on my own and it had the same result as using the brackets. Is that because something in the rest of the program wasn't right? >Stop returning the result of a void function. How do I get it to terminate, then? >The root cause of your problems is this design fault: you are mixing the cell update case with the end-of-line case. Mixing the regular case with the exceptional case is precisely what you should never do in a recursive design, because the result is spaghetti. This makes sense. In an iterative design you can generally do this. I guess I'm just not thinking with recursion yet. >The cell update branch should only do the cell update, display and recursion with +1. The end-of-line branch should check for end of loops, otherwise recurse by resetting ArrayEntry, swapping the in/out array order and increasing the loop counter. You'll need a loop counter parameter and you can dump the array copying entirely. That's a novel approach. You sound like you've done stuff like this before. In any case, it wouldn't be hard to have worked with recursion more than I have. >Here's some programming advice since you appear to be fairly new: make a clean design your top priority. The alternative, keeping a faulty design and patching it with an ever increasing number of fixes, is a path into the abyss. I'm not exactly new to programming, having some previous C++ experience, but I'm not a professional at it and I have hardly any experience with recursion. Plus it's been a while since I tried to do anything with programming, so my skills are kind of rusty.

>>6687 >It shouldn't do that because I had it inside an if-else statement which should only be triggered if ArrayEntry is at the end of a line. Actually I suppose this is exactly why it was looping infinitely, but under the current design ArrayEntry has to be reset to 0 in order to go through the next cycle of array evaluation. The design needs to be changed.

>>6688 Well, I mean it probably won't be changed to get rid of ArrayEntry, but something else needs to be there for cases where it's at the end of the line, because that seems to be the source of all the problems here.

>>6659 >void RecursiveECA90(int RecursiveECAInput[ColumnNum] You should go through K&R first so you don't make silly mistakes like this. K&R is extremely short, there's no reason not to go through it if you want to program in C.

how can you write a program with no recursion?

fun fact: iteration is actually a special case of recursion.

>>6692 >how can you write a program with no recursion? Just ask any COBOL programmer.

>>6693 No. Tail call recursion is a special case of iteration, and non-tail call recursion is expensive.

>>6696 >tail call recursion is a special case of iteration not 'a special case'. Tail calls and iterated loops are exactly equivalent, in languages which allow iteration over multiple variables simultaneously. In most languages, this isn't even true, and in that case iteration is actually a special case of tail calls. >non-tail call recursion is expensive which is irrelevant to the point. There are functions that cannot be implemented non-recursively, but there are no functions that cannot be implemented without loop constructs. Therefore iteration is a special case of tail calls.

>>6697 *function calls. A trivial example being the ackermann function. You can express it with function calls, but you can't express it with looping constructs.

>>6688 >>6689 The loop counter will take care of this. Or call it a row index. >>6687 >People seem to not like global variables in general. Is there ever a time when they're actually useful? Data that is constant once initialized and is used throughout a project, such as the fixed Huffman trees used by deflate. Unless you have a good reason to use them, avoid globals as they are bad for modularity and concurrency. >I thought it'd be simpler if I just stuffed all of it into RecursiveECA90, but maybe not. When you find yourself copy-pasting text blocks, chances are you need a function. >the tutorials I read said it was the same thing In this case it is equivalent but it's bad form. >How do I get it to terminate, then? You can use a plain return without a value when you have to, and a void function will also happily terminate when control flow reaches the end of its body. >In any case, it wouldn't be hard to have worked with recursion more than I have. When you have the time consider going over SICP. With a math background you'll find the math parts easy.

>>6655 No its not. If it were actually a modulo operator it would be, but this is C and % does not mean mod. It returns the (sometimes negative) remainder of integer division.

>>6655 >>6702 For instance, try calculating -15 mod 3 without the first %.

>>6697 >There are functions that cannot be implemented non-recursively No, there are not. You can always simulate the call stack with an actual stack and iterate. Same memory overhead as with non-tail-call-optimized recursion. Honestly, I don't get the point of this thread. "Recursive programming" is just a coding style. Personally I like how it looks, but it brings no benefits in a language without tail-call optimizations. When you get excited about recursion just for the sake of recursion, you sound like a newbie programmer that just managed to wrap their head around a new concept and is going through a major Dunning-Kruger phase about it. Case in point: class StackEntry attr_reader :m, :n, :case attr_accessor :result, :exec_point def initialize m, n @m = m @n = n if m == 0 @case = 1 elsif n == 0 @case = 2 else @case = 3 @exec_point = 0 end @result = nil end end M, N = 3, 4 stack = [StackEntry.new(M, N)] loop do current = stack.last result = nil if current.result stack.pop result = current current = stack.last if !current puts "Ackermann(#{result.m}, #{result.n}) = #{result.result}" break end end if current.case == 1 current.result = current.n + 1 elsif current.case == 2 if result current.result = result.result else stack.push StackEntry.new current.m - 1, 1 end else if current.exec_point == 2 current.result = result.result elsif current.exec_point == 1 stack.push StackEntry.new current.m - 1, result.result current.exec_point = 2 else stack.push StackEntry.new current.m, current.n - 1 current.exec_point = 1 end end end

>>6702 >>6704 First, you probably meant to give a non-congruent example since a (-15, 3) call gives 0 either way. Second, we aren't posting in a vacuum, but within something called a context, which you can find in >>6613. If you care to check, you will find that i covers [0..n), j is {-1,0,1} and thus i+j covers [-1..n]. Since the last value to exhibit a difference is -(n+1), the result is the same for the entire universe of values that the program will feed to that function, except one way is faster than the other and this happens to take place in the innermost loop of the program. Therefore >>The first %n is pointless. and putting it in amounts to slowing down your function in order to ensure correctness on inputs you know for a fact it will not be used on. This would be an exceedingly strange choice while at the same time choosing C as the programming language, presumably for speed. And third, if you check the overall discussion, you will find that the issue at hand is wrap-around of cell neighborhoods, and choosing a neighborhood size larger than the extent of the world would amount to a cell contributing to its own next state at least twice within the same frame step.

>>6699 >all this stuff I'll take this into account when I go back and try to fix this. Hopefully the next version will actually work. >When you have the time consider going over SICP. With a math background you'll find the math parts easy. My math background is basically engineering math. It goes up to differential equations and linear algebra. I hope that's enough.

>>6706 all you did is simulate function calls. That's recursivity right there.

>>6711 >all you did is simulate function calls. That's recursivity right there. That's a pretty vague definition of recursion you have there. Recursion usually refers to self-reference. I don't see any of that in there.

>>6710 >differential equations and linear algebra >I hope that's enough. You already know all the math SICP will introduce.

>>6706 > When you get excited about recursion just for the sake of recursion, you sound like a newbie programmer that just managed to wrap their head around a new concept and is going through a major Dunning-Kruger phase about it God yes. So many posts in this thread are so cringe because of this.