When to use recursion?

1

It is not clear to me when it is better to use recursion instead of loops. I know that the speed of response with recursion is better than that of loops, but I think the speed of response would only affect my program if there are too many iterations but when there are many iterations, recursion may give me an error and then it would not be a good idea use recursion.
I hope you understand me and someone can answer my question hehehe.

2

I would say that generally recursion is slower. You want to use recursion when you can’t use a loop, or at least can’t use it [recursion] cleanly.

1 Like
3

So just to get it out of the way all loops that can be written recursively, can also be written iteratively vice versa.

I personally would only reach for a recursive approach, if it makes sense for the given use-case. Usually anytime your dealing with a “recursive problem” you might find using recursion makes more sense then using a traditional loop. This doesn’t mean you have to use recursion, but it might make more sense.

Here’s an example I wrote in a codepen where I use a recursive function to calculate the size of a tree (the data structure, not the plant).

Code:

class Node {
  constructor(data, left, right) {
    this.data = data;
    this.left = left || null;
    this.right = right || null;
  }
}
// Returns the size of a given node, uses a recursive approach
const getSize = (node) => node 
  ? getSize(node.left) + getSize(node.right) + 1 
  : 0;

// Test data
const root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
console.log('size: ', getSize(root)); //size: 5

// Codepen: https://codepen.io/bradtaniguchi/pen/pojPJNP?editors=0012

// Translated from a python version:
// https://www.geeksforgeeks.org/write-a-c-program-to-calculate-size-of-a-tree/

Its possible to write an interative approach, but since the data structure is more or less recursive, using a recursive approach is much easier :smiley:

1 Like
4

That last sentence is the meat of it: recursive algorithms are a natural fit for recursively defined data structures (trees being the most common).

5

Duh. Of course recursive functions can always be translated into loops. It’s obvious now that someone mentioned it.

Not having a formal CS education can leave funny gaps in your knowledge.

6

I’ll use recursion when I need to manipulate list data structure without mutating any variables. Approaching tree data structure with recursion for example, should be much simpler than doing it with iterations/loops.

Also, in other languages like Haskell and Scheme, recursion instead of iteration is a preferred idiom when you need to do things repetitively.

1 Like
7

You don’t typically use much explicit recursion in real world Haskell unless you’re going for super-simple examples, or something like deriving an instance of Foldable for a new class. Usually you try to go with maps and folds over existing types, since ghc is pretty good about optimizing those, whereas it can’t deduce anything about by-hand recursion.

Recursion is a very low-level construct. But you still want to know recursion so you can recognize the recursive shape of things, see those shapes in your code, and implement the appropriate maps and folds on them.

1 Like