2

I wanted to know if there if any formal way of arguing in favor this. To be honest, I am not sure this is a good question but my purpose for asking is to know if we can always use trees as a mental model while thinking of recursion.

To paraphrase better, I want to know "Does every recursion formula correspond to a tree traversal?". Also, see my comments on Dirk's answer

The suggested duplicate question does not answer my question. My question has nothing to do with iteration.

abjoshi - Reinstate Monica
  • 372
  • 1
  • 13
  • 1
    ...Huh? Trees as a mental model for recursion? Not sure what you're asking here. Nearly every programming language in the world boils down to a tree somehow. Even the ones that don't support recursion. – cHao Feb 02 '18 at 23:01
  • Possible duplicate of [Can every recursive process be transformed into an iterative process?](https://stackoverflow.com/questions/7106656/can-every-recursive-process-be-transformed-into-an-iterative-process) – Mulan Feb 03 '18 at 01:29
  • @cHao edited. Is it clearer now? – abjoshi - Reinstate Monica Feb 04 '18 at 03:11
  • @abjoshi: Not really. *Literally everything* can correspond to a tree traversal, for some value of "tree" and "traversal". Likewise, one can come up with definitions by which it can't. Perhaps you should try coming up with an example of this mapping you're asking about -- that'd go a ways toward defining "tree traversal". – cHao Feb 04 '18 at 09:00
  • @cHao How about this. Given any recursive formula, is the evaluation of that formula equivalent to a tree traversal? For e.g., given the Fibonaccii recursion formula, you could represent the expansion by a tree and the evaluation as a post-order traversal of this tree. My question, then, is it possible to do this for *every* recursion ? – abjoshi - Reinstate Monica Feb 04 '18 at 12:02
  • As I said, it's possible to do that for *literally everything*, unless you narrow down your definitions. (If you do narrow them down enough to distinguish between recursion and iteration, though, you might not be able to fully represent the flow of infinitely recursive functions, particularly if they have side effects.) – cHao Feb 04 '18 at 15:12
  • not every function's trace is so small and well-behaved as the recursive Fibonacci. yes, small. check out the Ackermann function, and the 3n+1 function (i.e. Collatz function). Not a tree, lots and lots of trees, in the second. And lo-ots of *forests*, in the first. --- As for the distinction with a list, that's no distinction at all -- a list is also a tree, just a degenerate one (where a left child is always a leaf). – Will Ness Feb 17 '18 at 16:06

2 Answers2

2

When explaining recursion, tree traversal is a typical example. But, I would argue that not every recursion corresponds to a tree traversal:

In certain languages (lisp being one of them) recursion is used to realize iterations. There, you also have to express infinite loops with recursion, which I would assume does not fit your notion of "tree as mental model for recursion". (If you wonder how to implement an infinite loop with recursion and not run into stack overflows: There is a mechanism called tail call elimination which solves that problem.)

Dirk Herrmann
  • 5,550
  • 1
  • 21
  • 47
  • 1
    Scheme is better example since it really doesn't have control flows that isn't just syntax sugar for recursion. CL on the other hand does not guarantee TCO. – Sylwester Feb 03 '18 at 00:08
  • "I would argue that not every recursion corresponds to a tree traversal" . How about this argument? Say there are n calls in total, in a recursion. We represent each *callee* fn by a node. There is an edge between two nodes, "a" and "b", if a calls b. Then, there are exactly n-1 edges in the graph(since n-1 calls are needed for n-1 callees) which means it's a tree. Is this a plausible way of thinking? – abjoshi - Reinstate Monica Feb 04 '18 at 03:02
0

Below is recursive function which operates on integers, a non-tree-like input

const add = (x, y) =>
  x + y

const sumTo = (x = 0) =>
  x === 0
    ? x
    : add (x, sumTo (x - 1))

console.log (sumTo ())  // 0
console.log (sumTo (1)) // 1
console.log (sumTo (2)) // 3
console.log (sumTo (4)) // 10

Yet it evolves a tree-like (recursive) computation – sumTo (4)...

add ( 4
    , add ( 3
          , add ( 2
                , add ( 1
                      , 0
                      )
                )
         )
   )
// => 10

A tail-recursive version has a different computational process, though. This is distinction is the same made by Dirk Herrmann (another answer here)

const add = (x, y) =>
  x + y

const sumTo = (x = 0, acc = 0) =>
  x === 0
    ? acc
    : sumTo (x - 1, acc + x)

console.log (sumTo ())  // 0
console.log (sumTo (1)) // 1
console.log (sumTo (2)) // 3
console.log (sumTo (4)) // 10

In this case, when tail call elimination is available, sumTo (4) evolves an iterative computation

sumTo (3, 4)
sumTo (2, 7)
sumTo (1, 9)
sumTo (0, 10)
// => 10

So to answer your question, no. Recursive procedures (functions that reference themselves by their own name) may or may not evolve recursive processes.

This topic is talked about in Structure and Interpretation of Computer Programs, section 1.2.1

Mulan
  • 129,518
  • 31
  • 228
  • 259
  • I am trying to wrap my head around this. Meanwhile can you please look at my comment on Dirk Herrmann's answer and let me know if it makes sense to you? Also, I have edited the question details to make it clearer(hopefully) – abjoshi - Reinstate Monica Feb 04 '18 at 03:19
  • the reading i linked should help you – Mulan Feb 04 '18 at 03:54
  • I think I see what you are saying. In your 2nd example(tail call elimination), the 1st call to sumTo (3, 4) is not waiting for sumTo (2, 7) to finish. I guess the 2nd call can replace the 1st in the stack and so on. A call is converted to a jump. So it is not recursive in the "usual" sense that the callee returns to the caller and there is no tree traversal? Is that what your example means? – abjoshi - Reinstate Monica Feb 04 '18 at 08:16
  • Well your “usual sense” just needed some tuning, but yes, you’re seeing the subtle-but-important distinction. – Mulan Feb 04 '18 at 13:33
  • accepted because of the example, helpful link and the follow-up discussion – abjoshi - Reinstate Monica Feb 04 '18 at 14:09