Category:Recursion: Difference between revisions
m
Twiddle phrases. Twiddle the pseudocode?
(added Encyclopedia tag) |
m (Twiddle phrases. Twiddle the pseudocode?) |
||
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 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.
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
Recursion is often difficult for programming students to grasp, but it's not much different 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.
|