On using recursion in C

Question

While implementing a lexical analyzer in C, I found myself writing a recursive code:

// Return a List of Tokens
List Lexer_run(const char* input) {
    if(input[0] == '\0') {
        return new_List();
    } else {
        // ... Find Token and possibly advance in input for a few characters
        return List_add(Lexer_run(nextInput), newToken);
    }

Consider another example in an implementation of linked list

List_length(List* this) {
    if(!this) {
        return 0;
    } else {
        return 1 + List_length(this->next);
    }
}

I am wondering if I can always use such recursive code in C or if I should avoid it unless the case really requires recursion (for example recursive descent parser or a tree structure)

What I think so far

Advantages of recursion:

readable and elegant

Drawbacks:

will rapidly cause a stack overflow (in my computer it's around 1'000'000 calls)
can be inefficient comparing to an iterative version

Solutions:

use tail-call optimization and let the compiler transform my recursion into loops but I find tail-call code to be less readable.
Increase stack size for my program

Note

My question is not specifically about my examples but rather a general question if one should use recursion in C.

To answer to the only question in this post is: No, avoid it unless it brings something significant besides fewer keystrokes. — WhozCraig
– WhozCraig, Commented Jan 4, 2014 at 11:15
"I am wondering if I can always use such recursive code in C" - you can always use recursion, since C permits any function to call itself (even main()). You are also encouraged to write recursive code if it's more readable than its iterative counterpart. Yes, recursion can be slower. Yes, it can cause stack overflow. And that doesn't always matter -- don't optimize prematurely. — user529758
– user529758, Commented Jan 4, 2014 at 11:21
@WhozCraig I beg to differ. It's not about "fewer keystrokes". Recursion can be significantly easier to understand (and if I'm not inside a tight loop computing billions of floating-point numbers per second, I don't really care about the "efficiency" I lost with recursion if the code is more readable and easier to grasp.) — user529758
– user529758, Commented Jan 4, 2014 at 11:23
Nothing dictates that a recursive function must use recursion to all tasks -- a function parsing e.g. xml data or even a recursive descent parser can and should use both iterative and recursive control mechanisms where appropriate. — Aki Suihkonen
– Aki Suihkonen, Commented Jan 4, 2014 at 11:40

Sergey Kalinichenko · Accepted Answer · 2014-01-04 11:30:28Z

As a rule, you want to use recursion for tasks that are inherently recursive, such as walking recursive data structures, serializing structures defined recursively, or producing recursive structures from "flat" input (e.g. parsing a language). You do not want to apply recursion for tasks that can be expressed in terms of iteration, such as walking linear data structures.

Recursion is a powerful mechanism, but using it in place of iteration is like swatting a fly with a sledgehammer^*. Memory efficiency and a possibility of stack overflow are both very important considerations, but they are secondary to understandability of your code. Even if you eliminate the negative consequences of applying recursion where an iteration is sufficient by letting the compiler optimize tail call for you, readers of your program would be scratching their heads trying to understand first what you did, and then why you did it.

When you apply recursion to a recursive task (trees, recursive descent parsers, divide and conquer algorithms that process the entire input, searches with backtracking) your code becomes more readable, because it matches the task at hand. On the other hand, when you apply recursion to an inherently non-recursive task, your code becomes harder to read.

^* This metaphor on recursion vs. iteration is borrowed from an introductory chapters of one of Dijkstra's books.

Sneftel · Accepted Answer · 2014-01-04 11:18:17Z

2

Tail call optimization is frankly not to be trusted. There's too many gotchas which can scare the optimizer away from applying it in apparently innocuous cases. Be glad that it's there, but don't rely on it.

Because of this (and because of the fixed stack size), you generally want to avoid recursion unless you actually need its implicit stack structure [you don't, for your List_length]. Even then, be aware of the potential for stack overflows.

The primary benefit of writing recursive functions is readability. That makes them "first draft" material for algorithms like recursive descent which have a naturally recursive structure. Then rewrite them as iterative (with a stack as necessary) if/when you run into trouble.

A side benefit of doing things that way: you can keep the recursive version around as a reference implementation, and unit test them to ensure they are equivalent.

answered Jan 4, 2014 at 11:18

Sneftel

41.9k13 gold badges78 silver badges112 bronze badges

1 Comment

luk32 Over a year ago

+1 for the idea of leaving it around as a reference for testing. I think it's not as obvious as it should be.

Collectives™ on Stack Overflow

On using recursion in C

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related