CODEWITHSUNDEEP
cgccrecursion
Raphael S.Carvalho
Raphael S.Carvalho

Reputation: 11

GCC Compiler behavior in recursive functions

A few days ago, my professor said:

A function reuses the result (previously computed value) when it's called with the same value twice.

However, the result (previously computed value) being allocated in the heap memory.

He gave some examples, such as: Fibonacci recursive function.

Did he make a mistake?

Upvotes: 1

Views: 322

Answers (4)

Daniel Fischer
Daniel Fischer

Reputation: 183858

A function reuses the result(previously computed value) when it's called with the same value twice.

By default, no. You can memoize a function, so that it reuses already computed results, but that requires special intervention by the programmer (or possibly the compiler, but I'm not aware of any C compiler that does that).

It would be insanely expensive and wasteful to cache all computed values, since most functions aren't called repeatedly with the same arguments. And it is incredibly hard to find a good heuristic which calls are worth caching. Therefore such things are left to the programmer who hopefully has more knowledge of what functions it is worth to cache.

Upvotes: 4

Neil
Neil

Reputation: 55392

Not quite the same, but I've seen reports of gcc performing inlining of recursive functions. Take the example of the fibonacci function, f(x) = f(x - 1) + f(x - 2); apparently gcc can inline the call to f(x - 1) resulting in f(x) = 2f(x - 2) + f(x - 3) and then use tail recursion optimisation to turn this into a loop: f(x) = 2f(x - 2) + 2f(x - 5) + ... + f(x % 3). There's still some recursion there, of course, but it's a lot less.

Upvotes: 0

Mahmoud Al-Qudsi
Mahmoud Al-Qudsi

Reputation: 29519

Actually, memoization has become (to some extent) part of the C++ standard with C++11. You can take a look at this intro to automatic memoization of recursive functions using new C++11 features.

Edit:

This question is for C not C++. I missed that. This answer is inapplicable; I'd delete it, but there aren't many other memoization questions on here and there's a good chance it'll help someone.

Upvotes: 3

Tilman Vogel
Tilman Vogel

Reputation: 9773

gcc by itself will not cache any previous results but of course, for many recursive functions, it makes perfect sense to implement caching of previously calculated values.

So, if he claimed, gcc takes care of this caching, he made a mistake. I guess, he rather referred to some specific implementation of e.g. the Fibonacci function.

Upvotes: 2

Related Questions