CODEWITHSUNDEEP
algorithmdata-structuresrecursion
user1113314
user1113314

Reputation: 839

Implementing recursion without a separate function

I was wondering how (or maybe even if it's possible) to implement recursion without a separate function that calls itself. So far all algorithms implementing recursion I've seen use a separate function. I thought a lot and came up with the idea that a goto statement with some variable mutation can do the job but I'm really unsure about that. I made a mini research and found info about this Structured programming theorem which proves that every algorithm can be implemented with only three data structures, so such a recursion implementation must be posible but I still cannot assemble everything into consistent knowledge and understanding for the whole would-be approach.

Upvotes: 2

Views: 4139

Answers (3)

Samy Arous
Samy Arous

Reputation: 6814

What you are looking for is basically expressing a recursive function into an iterative form. This can easily be done by using a Stack. Here's a very simple example in C#:

int NodeCount(Node n)
{
      if (n.Visited) return 0; // This node was visited through another node, discard
      n.Visited = true;
      int res = 1;
      foreach (Node ni in n.Children) // Recurse on each node
      {
            res += NodeCount(ni); // Add the number of sub node for each node
      }
      return res;           
}

Here's the exact same function in iterative form:

int NodeCount(Node root)
{
    int res = 0;
    Stack<int> stk = new Stack<int>();
    stk.Push(root) // We start with the root node
    while( stk.Count > 0) // While we still have nodes to visit
    {
          Node current = stk.Pop(); // Get the node on top of the stack
          current.Visited = true;  // Mark it as visited
          res ++; // Add one to the count
          foreach (Node ni in n.Children) // Push all non visited children to the stack
          {     
                if (ni.Visited == false) 
                        stk.Push(ni);
          }

    }
    return res;
}

Upvotes: 3

Tyler Durden
Tyler Durden

Reputation: 11562

You can perform a sort of a recursion without a function using any stack-based language. For example, in Forth you can write the fibonacci function like this:

: fibonacci 0 1 10 0 do 2dup + rot . loop swap . . ;

This program recursively generates 10 iterations of the fibonacci sequence, each iteration using the inputs from the previous iteration. No function is called.

Upvotes: 1

Cratylus
Cratylus

Reputation: 54094

to implement recursion without a separate function that calls itself.

Yes it is possible to convert a recursive algorithm to an iterative one. But why would you want to use a goto statement? When you make a function call the assembly generated has a branch instruction to jumb to the specific function which acts similar to a goto.
So what you would accomplish is somewhat similar to what the machine code would eventually do, with the benefit of avoiding stack frame calls and the disadvantage of the horrible spaggeti code from using goto.
If you want to avoid recursion, use iteration. How did you come up with this question?

Upvotes: 1

Related Questions