Category:Recursion: Difference between revisions

Line 9:

'''return''' ''end condition value''

More than one end condition is allowed. More than one recursion condition is allowed.

Recursion is often difficult for programming students to grasp, but it's not much different than any other function call. In a normal function call, execution moves to another function with the given parameters. In a recursive function call, execution moves to the same function, but the parameters still act as they would in a normal function call.

Many recursion problems can be solved with an iterative method, or using a [[loop]] of some sort (usually recursion and iteration are contrasted in programming, even though recursion is a specific type of iteration). In some languages, the factorial example is best done with a loop because of function call overhead. Some other languages, like [[Scheme]], are designed to favor recursion over explicit looping, using tail recursion optimization to convert recursive calls into loop structures.

Line 16:

Line 18:

The benefits of this optimization are primarily [[System stack|stack]] related. Transforming recursive functions into iterative functions can save memory and time.

Memory is saved by reducing an entire call stack to one function call. This way, more complex calls can be evaluated without running out of memory.

Memory is saved by reducing an entire call stack (with contexts for each call) to one function call. This way, more complex calls can be evaluated without running out of memory.

Time is saved because each function return takes a long time relative to a simple branch. This benefit is usually not noticed unless function calls are made that would result in large and/or complex call trees. For example, the time difference between iterative and recursive calls of <tt>fibonacci(2)</tt> would probably be minimal (if there is a difference at all), but the time difference for the call <tt>fibonacci(40)</tt> would probably be drastic.