CODEWITHSUNDEEP
ctail-recursion
Ngo Thanh Nhan
Ngo Thanh Nhan

Reputation: 513

Is Tail recursive really powerful on C language?

I think the Tail-recursive is really helpful in functional programming language. How about C?

From wiki:

Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls).

The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination.

Upvotes: 0

Views: 563

Answers (4)

R Sahu
R Sahu

Reputation: 206627

The C standard does not specify tail recursion as part of the language at all. The only thing the C99 standard says about recursive function calls is:

6.5.2.2 Function Calls

11 Recursive function calls shall be permitted, both directly and indirectly through any chain of other functions.

If a compiler can detect tail recursion and translate a recursive call as tail recursion, it can but it is not required to do so by the standard.

Upvotes: 1

geocar
geocar

Reputation: 9305

ANSI (standard) C doesn't require tail recursion. Most C compilers implement it because the optimisation isn't very complicated and it provides a huge savings in stack and cache memory.

Pre-ANSI, however, C definitely supported tail recursion. It was done with goto:

fact(n,m) { m =+ n; n--; if(n) goto fact; return n; }

Note other oddities: += was spelled =+ and int is the default for all variables. Source code examples of pre-ansi C are uncommon now, but the v6 ed.c notably uses this method for error handling.

Upvotes: 1

Zbynek Vyskovsky - kvr000
Zbynek Vyskovsky - kvr000

Reputation: 18825

Tail-recursive is usually used in functional languages because it's natural way to implement loops on structures which are actually not that much recursive in procedural languages.

Therefore procedural languages don't need it. However, it's up to compiler to decide if it finds such optimization.

Upvotes: 4

Vlad from Moscow
Vlad from Moscow

Reputation: 311038

Neither the C Standard nor compilers have to support the tail recursion. It is implementation defined whether a compiler supports the tail recursion.

Upvotes: 2

Related Questions