Implementing recursion without a separate function

Question

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.

Recursion is pretty much defined by a function calling itself. However, every recursion can be reproduced using a loop and a stack. — amit, Sep 21 '12 at 20:07
In lambda calculus, you can use a [Fixed-point combinator](http://en.wikipedia.org/wiki/Fixed-point_combinator) to create anonymous recursive lambda functions. I've done it in Python a couple times for fun, although I don't know if it has a practical use. Edit: for example, here's the Fibonacci function: `(lambda f: lambda x: f(x,f))(lambda x, f: 1 if x < 1 else f(x-1,f) + f(x-2,f))(5)` — Kevin, Sep 21 '12 at 20:20

score 3 · Accepted Answer · edited Jun 14 '19 at 10:37

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;
}

Thanks for the example, but I just wanted a way to implement recursion without a function rather than a different approach(iterative) to the algorithm — user1113314, Sep 21 '12 at 20:39
@user1113314: there's no function here which calls itself, it matches your description. — Karoly Horvath, Sep 21 '12 at 20:49
@user1113314: even though it seems to be a different approach, this is actually the same. If you add a trace to see in which order the nodes are discovered, you'll notice that it is exactly the same order. This is due to the fact that a computer can only run iterative code (And it actually have no notion of function). The recursion is emulated at the lowest level by using a stack just like I did (Well technically, there are some differences) and some goto calls. — Samy Arous, Sep 21 '12 at 21:16

score 1 · Answer 2 · answered Sep 21 '12 at 20:24

1

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?

answered Sep 21 '12 at 20:24

Cratylus

52,998
69
209
339

I just wondered how could be implemented without function(curiosity), not that I want to use such an approach. I haven't seen an implementation without using a function and found it challenging to come up with one so I asked the community for help. – user1113314 Sep 21 '12 at 20:35
@user1113314:Look http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration or http://www.refactoring.com/catalog/replaceRecursionWithIteration.html – Cratylus Sep 21 '12 at 20:40

score 1 · Answer 3 · answered Sep 21 '12 at 21:21

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.

Implementing recursion without a separate function

3 Answers3