Concept Question
I am going over some concept questions in my textbook in the section for recursion. I have never seen anything like this before, and it doesn't really engage me. My question is geared toward those who have been through the schooling process. I am curious if this kind of stuff is going to be a reoccurring theme that I should be sure to sharpen up on? Or, is it more of a conceptual exercise (that will pass) to help aid in the process of recursive thinking?
An example:
An example:
|
|
Recursion is indeed a very important concept to understand. Many problems are made easier by thinking in terms of recursion.
This here, however, is a grammar, which is a core concept in pattern matching, used in all kinds of stuff. You will likely get into some simple text processing, but it goes right to the core of computer theory.
(I presume in your example that that first <s> was meant to be an upper-case <S>? — Or that case does not matter in this notation?)
To understand it, simply take one thing at a time. Let us take a string like
What about
And much like solving a maze by keeping your hand on a wall, you can work your way through this by using repeatable behaviors when processing it. For example, in question ‘a’ you can easily use the <D><S><S> sequence to list all possible three-character strings. Naturally, the first character must begin with a <D>, which is only one of two characters: 1 or 2.
Following to the first <S>, what would happen if I chose <S> to expand to <D><S><S> again? Would the final string still be three characters long?
Good luck!
This here, however, is a grammar, which is a core concept in pattern matching, used in all kinds of stuff. You will likely get into some simple text processing, but it goes right to the core of computer theory.
(I presume in your example that that first <s> was meant to be an upper-case <S>? — Or that case does not matter in this notation?)
To understand it, simply take one thing at a time. Let us take a string like
1AB. Is that a string that is accepted by your grammar? How can you tell?What about
AB1? Can is that acceptable? Why or why not?And much like solving a maze by keeping your hand on a wall, you can work your way through this by using repeatable behaviors when processing it. For example, in question ‘a’ you can easily use the <D><S><S> sequence to list all possible three-character strings. Naturally, the first character must begin with a <D>, which is only one of two characters: 1 or 2.
Following to the first <S>, what would happen if I chose <S> to expand to <D><S><S> again? Would the final string still be three characters long?
Good luck!
recursion is, more or less, a loop with a 'free' stack data structure. You can do anything without it, but often the code is more than 3x the size and complexity to do so. It makes a lot of simple problems much easier, like destroying every node in a tree container, try doing that without it, and you find yourself with a bit of a mess, with it, it s like 5 lines of code.
As nice as it is, I would not spend a great deal of time on it. Most recursive functions are small so if you can do something like the above, you know enough. If not, maybe brush up a little, but its a day or 2 of work, not something to burn weeks on.
The language theory stuff is a deep, complicated rabbit hole. It has little use for most practical coding, but is critical if you want to make a language or something like a language (even a file format that is complicated will use a bit of this).
As nice as it is, I would not spend a great deal of time on it. Most recursive functions are small so if you can do something like the above, you know enough. If not, maybe brush up a little, but its a day or 2 of work, not something to burn weeks on.
The language theory stuff is a deep, complicated rabbit hole. It has little use for most practical coding, but is critical if you want to make a language or something like a language (even a file format that is complicated will use a bit of this).
I have to disagree, strongly, on both your points.
The differences between a recursive and an iterative solution are small, and until C++ can guarantee tail recursion a lot of code will still be written iteratively to accommodate it. But the problem is still reasoned by recursive thinking.
Language theory is not complicated or scary, and has both imminent and profound impact on almost all practical coding. The fact that so few people bother to understand any of it is, in my opinion, much of the reason that so much code is broken today — they do not know how to analyze their own design.
The differences between a recursive and an iterative solution are small, and until C++ can guarantee tail recursion a lot of code will still be written iteratively to accommodate it. But the problem is still reasoned by recursive thinking.
Language theory is not complicated or scary, and has both imminent and profound impact on almost all practical coding. The fact that so few people bother to understand any of it is, in my opinion, much of the reason that so much code is broken today — they do not know how to analyze their own design.
Im not sure we disagree on the first point too much. I agree its reasoned recursively, and I agree some code is written with iteration for various reasons. I think the only disagreement is that I feel that many simple recursive functions more than double in size to do iteratively, which depends on the problem (factorial, its no more complex, destroying a list or tree, its a fair bit more because you have to track the stuff that was on the call stack yourself). I don't think I ever saw a small and clean 8 queens iteration, for the extreme side.
The second point, I would hear more... what do you use the theory for as you design?
The second point, I would hear more... what do you use the theory for as you design?
Last edited on
I appreciate the feedback guys. It helps to hear from those who been through it. I'll keep the thread open for a little just in case any conversation wants to carry on.
Topic archived. No new replies allowed.