1

I'm trying to grasp the relation between iteration and recursion by trying to model a simplified execution of a body of statements within a scope { } on an old homework assignment I had. Let's say I have two statement types: while statement, and an assignment statement.

For now, I'm assuming the while statement's condition is always true. EDIT: Also, assume the while statement only executes once (i.e, I should have called it an if statement)

In recursion, this would be simple:

executeBody( body )
{
  for each stmt in body
  {
    switch (stmt)
    {
      case ASSIGNMENT:
       // work
       break;

      case WHILE-STMT:
        executeBody(whileStmt->body)
        break;
    }
  }
}

But, I'm having trouble doing this for iteration. I know I need to simulate a stack, but I just can't conceptualize how to execute all the statements in a while statement before I go to the next statement. Here's a model of what I have:

executeBody( body )
{
  for each stmt in body
  {
    case ASSIGNMENT:
      // work
      break;

    case WHILE-STMT:
    {
       stack< body > stack;
       stack.push(whileStmt->body);     
       while (stack isNotEmpty)
       {
          for each stmt (in each body) in stack
          {
            case ASSIGNMENT:
              // work;
              break;

            case WHILE-STMT:
              //stack.push(this_whileStmt->body);
              // ????
              break;
          }
       }
    }  
  }
}

EDIT: Changed the recursion example to show that the body is a sequence of statements.

4

2 回答 2

2

首先，我会放弃你的外循环。这是多余的。

   stack< body > stack;
   stack.push(body);     
   while (stack isNotEmpty)
   {
      for each stmt (in stack.pop()) // pop the top statement off of your stack
      {
        case ASSIGNMENT:
          // work;
          stmt.Remove()
          /*you don't need to break here.  just go onto the next operation*/

        case WHILE-STMT:
          stack.push(stmt->body);
          stmt.Remove()
          stack.push(stmt); 
          break;
      }

一旦你遇到这种WHILE-STMT:情况，代码就会中断并继续处理堆栈的顶部项目，这是你刚刚放在那里的代码块。

一旦该块完成执行，它将从堆栈中弹出（您在for声明中执行此操作），并且它将与您当前的块一起恢复。清除当前语句并将工作块推回堆栈的全部目的是为了能够像这样恢复。

于 2013-05-01T18:30:59.613 回答
1

你有堆栈在错误的地方。它应该在 executeBody 例程的顶部声明。看一下这个：

executeBody(body) {
    stack<body> work;

    stack.push(body);

    while (stack isNotEmpty) {
        item = stack.pop();
        switch (item) {
            case ASSIGNMENT:
                // work;
                break;
            case WHILE-STMT:
                stack.push(item);
                break;
        }
    }
}

这个伪代码应该清楚地表明你所有的身体都在堆栈上。他们中的一些人做分配，一些人做同时。

于 2013-05-01T18:26:16.517 回答