Can anyone tell me the main difference between an inline function and recursive function?
+11
A:
These are unrelated concepts.
An function may be declared inline, which signals to the compiler that any calls to the function should be replaced by an implementation of the function directly at the point the call is made. It's vaguely like implementing some piece of logic as a macro, but it retains the clean semantics of a normal function call.
A recursive function is simply one that calls itself.
Note that the inline keyword is just a suggestion. The compiler is free to ignore it whenever it wants.
Also note that a recursive can also be declared inline. The compiler may, in principle, be able to inline a recursive function by transforming it into an iterative algorithm inside the calling function. However, recursion is usually one of the things that will make a compiler give up on inlining.
Marcelo Cantos
2010-05-09 10:50:24
Not true, tail-recursion is a common optimization in modern day compilers, and THE thing that makes functional languages like haskell and f# work.
Blindy
2010-05-09 10:59:46
@Blindy: Which of my statements is not true?
Marcelo Cantos
2010-05-09 11:04:51
Tail-recursion is THE thing that makes functional languages work? Not true at all, it's an optimization in order to decrease the stack space use and to improve efficiency and there's nothing that *requires* it. Other than it makes it more efficient of course. Furthermore Common Lisp's standard does not define it although most implementations do.
Jonas
2010-05-09 11:21:27
The "However, recursion is usually one of the things that will make a compiler give up on inlining" part. And because functional languages don't have loop constructs, they do everything using recursion, not having tail-recursion optimizations would cause stack overflows on the most basic loops.
Blindy
2010-05-09 11:30:07
@Jonas: That is not true. The guaranteed presence of TCO changes the semantics of the language in a significant way: Only *with* this guarantee may the programmer use unbounded recursion. Indeed, for FP languages that specify TCO, TCO becomes a central semantic property that allows the correct operation of a whole category of programming that would have to be written differently in the absence of TCO. See this question and my two comments: http://stackoverflow.com/questions/1888702/are-there-problems-that-cannot-be-written-using-tail-recursion
harms
2010-05-09 12:12:01
Just to be nitpicky, to "A recursive function is simply one that calls itself" I would add "directly or indirectly". You can have e.g. a pair of functions, none of which are calling itself directly, still exhibit recursive behaviour.
Péter Török
2010-05-09 13:10:33
@harms: Good point, I stand corrected.
Jonas
2010-05-09 14:29:27
@Blindy: The question was tagged as C++, for which that statement _is_ true. I don't know what point you're trying to make with the second remark. Yes, some (very few) functional languages do not have explicit loops, but even those might still execute a recursive function using a while loop at the machine code level. How did tail-recursion come into this, anyway?
Marcelo Cantos
2010-05-09 14:35:02
@Péter: I wouldn't add "directly or indirectly". A pair of functions achieves recursion, but it is the pair, as a system, that is recursive, not the individual functions. Perhaps this is a subjective issue, though; I have had a look and failed to locate a definition of "recursive function" that explicitly includes or excludes indirect recursion.
Marcelo Cantos
2010-05-09 14:45:07
@Marcelo: I'd lean towards including it. Otherwise you could take any recursive function and make it "non-recursive" just by having it call itself through a trivial wrapper. That seems to me to be a very useless definition of recursive from the POV of the programmer or computer scientist. It might be useful from the POV of a compiler-writer to distinguish between the two cases, simply because "direct" recursion is a special case that's trivial to identify (well, ignoring function pointers).
Steve Jessop
2010-05-09 17:18:48
@Steve: Thank you for offering this perspective. However, while I am still in two minds about it overall, I don't think that the ability to create a contrived wrapper materially affects this issue. In fact, what you are talking is in spirit (not so much in the details) what happens with fixed point combinators. The combinator takes a non-recursive function and transforms it into a recursive one. Your interpretation would declare all such higher order functions to be recursive. And yet, descriptions of fixed point combinators invariably refer to these functions as non-recursive.
Marcelo Cantos
2010-05-09 22:14:31
I haven't studied lambda calculus formally, so I'd have to take your word for that. I note that the Wikipedia article says, 'in lambda calculus all abstractions are anonymous, and that the names we give to some them are only syntactic sugar. Therefore, it's meaningless in this context to contrast FACT as a recursive function with F as somehow being "not recursive"'. FACT is the fixed point of F in that example. Taking a step back, it's an imperative implementation detail whether a factorial function is *call-recursive* or uses a loop: lambda calculus doesn't concern itself with such details.
Steve Jessop
2010-05-10 09:25:16
+1
A:
A recursive function is a function that calls itself.
An inlined function is a function, that is "inserted into another function", i.e. if you have an inlined function add(a,b), and you call it from a function func, the compiler may be able to integrate the function body of add into the body of func so the arguments don't need to be pushed onto the stack.
phimuemue
2010-05-09 10:50:31
+2
A:
These are two very different concepts.
99% of programming languages allow recursive functions. A recursive function re-calls it's self to get something done. Most recursive functions can be rewritten as loops.
E.g. Simple recursive function.
int Factorial(int f)
{
if(f > 1)
return f * Factorial(f-1);
else
return 1;
}
An in-lined a function is a hint to the compiler that you don't want the processor to jump to this function, instead just include the op-codes for the function where ever it is used. This builds faster code for some calls one some architectures. Be aware that most modern compilers targeting non-embedded processors will choose to ignore your "inline" hints, and will choose what to inline itself.
Hope this helps, apologies if badly formatted, typed on my I-phone.
Binary Worrier
2010-05-09 11:00:35