Category:Recursion: Difference between revisions

← Older edit

Category:Recursion (view source)

Revision as of 11:29, 3 September 2017

914 bytes added , 6 years ago

m

Twiddle phrases. Twiddle the pseudocode?

Dinosaur

1,220

edits

Revision as of 19:36, 29 October 2009 (view source) rosettacode>Mwn3d (Added note about students having difficulty with recursion based on experience) ← Older edit		Latest revision as of 11:29, 3 September 2017 (view source) Dinosaur (talk \| contribs) m (Twiddle phrases. Twiddle the pseudocode?)
(2 intermediate revisions by 2 users not shown)
Line 1: [[Category:Solutions by Programming Task]][[Category:Encyclopedia]]'''Recursion''' is the idea that a function can come to an answer by repeatedly calling itself with new arguments until a "base case" or "end condition" is met. One ~~good~~simple example is a [[factorial function]] (for positive integers only). The base case for factorial is "0!" (some people like to use 1 or 2, but 0 is OK for instructional purposes). When 5 is sent as an argument to a recursive factorial function, the function does not know the answer right away. ~~All~~But it ~~knows~~does isknow that 5! = 5 * 4!. So it calls itself to find out what 4! is. This process continues until it gets to 0!, which is 1. Now it has built up a train of answers: 5! = 5 * 4! = 5 * 4 * 3! etc., and it can find the final answer. Other common examples include [[tree traversal]] and the [[wp:Minimax\|min/max algorithm]]. Anyone who can convert the likes of 12,345 into "twelve thousand, three hundred and forty-five" is engaging in the recursive use of language. A pseudocode function to demonstrate recursion would look something like this: Line 8: '''else''' '''return''' ''end condition value'' More than one end condition is allowed. More than one recursion condition is allowed. More generally, the function may be able to deliver the result for some arguments but not for others, and for those cases it is able to compose the result from some combination of function calls with different arguments. Simple recursion is when it invokes itself, but a group of functions may be involved in mutual recursion. The analyst's task is to devise a plan that will always end with a result for the desired initial invocations. In the case of the factorial function, this is easily seen since factorial(n) invokes factorial(n - 1) and so on: for every positive integer this sequence must eventually reach zero and the result for factorial(0) is directly available. A more complex example is provided by the [[wp:Ackermann_function]] ~~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~~from 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.