RECURSION
T: 051 401 2754 itinfo@[Link] [Link]/it
OBJECTIVES
• Array
• ArrayList
T: 051 401 2754 itinfo@[Link] [Link]/it
WHAT IS RECURSION?
• Sometimes it is necessary to write a method
which needs to call itself when processing data
– Can you think of an example?
• These methods are generally called recursive
functions (or recursive methods in C#)
• Recursive functions are usually query functions
• Incorrectly coded recursive functions may run as
infinite loops, so always include an escape
condition in your code
Recursion is a programming
technique in which a method makes
a call to itself to solve a particular
problem. Such methods are called
recursive.
EXAMPLE: FACTORIAL
• <<worked example>>
n!
EXAMPLE: FIBONACCI SEQUENCE
• <<worked example>>
Formula:
Seed values:
F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 F17 F18 F19
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
DIRECT AND INDIRECT
When in the body of a method there
is a call to the same method, we say
that the method is directly
recursive. If method A calls method B, method
B calls method C, and method C calls
method A we call the methods A, B
and C indirectly recursive or
mutually recursive.
When using recursion, we have to be
totally sure that after a certain count
of steps we get a concrete result. For
this reason we should have one or
more cases in which the solution
could be found directly, without a
recursive call. These cases are called
bottom of recursion.
If we set the value of n = 100, the
calculations would take so much time
Avoid recursion, unless you that no one would wait to see the
are certain about how it result. The reason is that similar
works and what has to implementation is extremely
happen behind the scenes. inefficient. Each recursive call leads
Recursion is a great and to two more calls and each of these
powerful weapon, with calls causes two more calls and so
which you can easily shoot on. That's why the tree of calls
yourself in the leg. Use it grows exponentially as shown on
carefully! the figure below.
RECURSION OR ITERATION?
• If by using recursion we reach a simpler,
shorter and easier to understanding
solution, not causing inefficiency and
other side effects, then we can prefer
recursive solution. Otherwise, it is better
to think of iteration.
MORE ABOUT RECURSION AND
ITERATION
Generally, when we have a linear
computational process, we do not
have to use recursion, because
iteration can be constructed easily
and leads to simple and efficient
calculations.
What is distinctive about the linear
computational processes is that on
each step of the calculating
recursion is called only once, only
in one direction.
In tree-like (branched)
Use recursion for branched computational processes on each
recursive calculations (and step of the recursion a couple of
ensure each value is recursive calls are made and the
calculated only once). For scheme of calculations could be
linear recursive calculations visualized as a tree (and not as a list
prefer using iteration. like in linear calculations).
FOR NEXT LESSON...
T: 051 401 2754 itinfo@[Link] [Link]/it
REFERENCES
• [Link]
namespace/1045329 accessed 2012-01-19
• [Link]
us/library/ct363x9h(v=vs.80).aspx
• [Link]
us/library/2s05feca(v=vs.71).aspx
T: 051 401 2754 itinfo@[Link] [Link]/it