CS 121 Lecture Notes - Lecture 77: Koch Snowflake, Fractal
Recursion Vs. Iteration:
1 way to compute sum of the #s between 1 & num inclusive in an iterative
manner is like this:
sum = 0;
for ( int number = 1; number <= num; number++)
sum += number;
oThis way is more straightforward than recursive version.
Recursion has overhead of multiple method invocations.
oIn this case, recursion presents a more complicated solution than
iterative counterpart.
oProgrammers must learn when to use recursion & when not to use it.
oDetermining which approach is best depends on the problem being
solved.
oAll problems can be solved an iterative manner.
In some cases, iterative version is much more complicated.
oFor some problems, recursion allows us to create relatively short &
elegant programs.
Direct Vs. Indirect Recursion:
Direct Recursion: when a method invokes itself.
oEX: A sum calls a sum.
Indirect Recursion: when a method invokes another method, eventually
resulting in the original method being invoked again.
oMethod invocations are shown with solid lines.
oReturns are shown with dotted lines.
oEntire invocation path is followed & recursion unravels following the
return path.
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
In some cases, iterative version is much more complicated: for some problems, recursion allows us to create relatively short & elegant programs. Direct recursion: when a method invokes itself: ex: a sum calls a sum. Indirect recursion requires all the same attention to base cases that direct recursion does. Indirect recursion can be more difficult to trace b/c of intervening method calls. Extra care is warranted when designing/evaluating indirectly recursive methods. Ensure indirection is truly necessary & clearly explained in documentation. The concept of recursion has several uses in images & graphics: fractal: a geometric shape that can be made up of the same pattern repeated at different scales & orientations. The nature of a fractal lends itself to a recursive definition. Computers have made fractals much easier to generate & investigate. Begins w/ an equilateral triangle, which is considered to be the.