Answered Convert a C# Recursive Method to Iterative

je79

New member
Joined
Feb 11, 2021
Messages
1
Programming Experience
10+
I've got a method for a parser that looks like so:
C#:
public List<SequenceTokenTableState> BuildSequenceTokenTableRecursive(string sequenceName = "", int level = 0, List<string> breadCrumbs = null, bool skipAddedEntries = true, bool printOnConsole = false)
{
    List<SequenceTokenTableState> list = new List<SequenceTokenTableState>();
    if (!string.IsNullOrEmpty(sequenceName))
    {
        var seq = new ParserSequence();
        if (SequencesDictionary.ContainsKey(sequenceName))
        {
            seq = SequencesDictionary[sequenceName];
        }
        else { return new List<SequenceTokenTableState>(); }
        for(int i=0;i<seq.Sections.Count;i++)
        {
            var sec = seq.Sections;
            if (sec.HasTokens || sec.HasDynamicRules) {
                if (sec.HasTokens)
                {
                    foreach(var token in sec.Tokens)
                    {
                        list.Add(new SequenceTokenTableState()
                                 {
                                     CallEnum = CallEnum.LexerCheckStart,
                                     Comments = InputLexer.RulesDictionary[token].RuleName + "/{" + InputLexer.RulesDictionary[token].StringToken + "} Opt:" + sec.IsOptional + " Rep:" + sec.IsRepeating,
                                     Level = level
                                     });
                    }
                }
                if (sec.HasDynamicRules)
                {
                    foreach(var rule in sec.DynamicRules)
                    {
                        list.Add(new SequenceTokenTableState()
                                 {
                                     CallEnum = CallEnum.LexerCheckStart,
                                     Comments = InputLexer.RulesDictionary[rule].RuleName + ":::Dynamic/{" + InputLexer.RulesDictionary[rule].StringToken + "} Opt:" + sec.IsOptional + " Rep:" + sec.IsRepeating,
                                     Level = level
                                     });
                    }
                }
            }
            if (sec.HasSequences)
            {
                for (int ii = 0; ii < sec.Sequences.Length; ii++)
                {
                    var seq1 = sec.Sequences[ii];
                    var rundata = BuildSequenceTokenTableRecursive(seq1, level + 1);
                    list.Add(new SequenceTokenTableState()
                             {
                                 CallEnum = CallEnum.GetMethodCallResult,
                                 Level = level,
                                 InnerStates = rundata,
                                 SequenceName = seq1,
                                 Comments = "Opt:" + sec.IsOptional + " Rep:" + sec.IsRepeating
                                 });
                }
            }
        }
        return list;
    }
    return new List<SequenceTokenTableState>();
}
It's a bit long, but the major thing I want you to notice is that it calls itself within an if, for, if, and for loop. The method is essentially doing a preorder tree traversal.

I want to convert that over to an iterative method using a Stack, but don't know how, especially given that C# does not let you jump into a loop with a goto statement, which makes good sense.

If you don't know, no worries, just saying hello I'm a new member here!
 
Last edited by a moderator:

jmcilhinney

C# Forum Moderator
Staff member
Joined
Apr 23, 2011
Messages
3,921
Location
Sydney, Australia
Programming Experience
10+
The Inline code button is for inline code, i.e. small snippets of code that you include within a line of text, e.g.
I want to handle the Click event of a Button.
For blocks of code, please use the Code button. As you can see from my edit to your question, the formatting it provides is far more thorough and readable.
 

jmcilhinney

C# Forum Moderator
Staff member
Joined
Apr 23, 2011
Messages
3,921
Location
Sydney, Australia
Programming Experience
10+
As for the question, what C# can do is not something that need concern you to begin with because you should be working out the logic first, before even considering writing code. No matter the task you're attempting to achieve, you should start by considering how you would perform it manually, e.g. with pen and paper. You can then refine and formalise the steps you come with into an algorithm. You can test that algorithm multiple manual tests to make sure it works. Once you have a working algorithm, THEN you can write C# code to implement it specifically. That way, you always have something to compare the code to to make sure that it is actually doing what it is supposed. You can also debug to identify exactly where to actual behaviour may differ from your expectations. If you encounter an issue, you can then provide us with far more specific and relevant information about that issue. Rather than "I want to do X, show me how", you can show us exactly what you're trying to implement and how, as well as explain exactly where and how it breaks down and what the actual inputs and outputs were at the time. That is software development, as opposed to code writing.
 
Top Bottom