![Tower of Hanoi
function hanoi is:
input: integer n, such that n >= 1
1. if n is 1 then return 1
2. return [2 * [call hanoi(n-1)] + 1]
end hanoi
Interestingly, graphical representation of tower of
hanoi is similar to that of sierpinski arrowhead curve
Recursive
Call](https://image.slidesharecdn.com/presentation-151213175934/85/Awesome-Introduction-to-Recursion-in-Programming-with-Fractals-33-320.jpg)
More Related Content
Viewers also liked (17)
Similar to Awesome Introduction to Recursion in Programming with Fractals (20)
Recently uploaded (20)
Awesome Introduction to Recursion in Programming with Fractals
- 1. Intro to Recursion in Programming with Fractals @gurpalsingh204 Presentation version of blog post on Singhcodes.wordpress.com
- 2. What is recursion? Recursion simply is applying a procedure, breaking it into smaller parts, and applying the same to the smaaller parts. Example: Fibonacci series: F(n) = F(n-1)+F(n-2) Usually one has to get some experience before getting a good feel of the concept. But if you could see what happens under the hood you could get a better understanding more quickly. Fractals are perfect for this purpose besides being beautiful.
- 3. What are fractals? A Fractal, basically, is a repeating pattern. Each smaller part of the fractal is identical to the bigger part. If you zoom into an ideal fractal, you couldnt tell how much you have zoomed in.
- 4. An Example of fractals The mandelbrot set is a famous fractal
- 5. Let's make some fractals!
- 6. The Koch Line We will begin with the simplest fractal : The Koch Line The rule to make Koch line: 1.Draw (an imaginary) straight line. 2.Split it into three equal parts. 3.Replace the middle part with an equilateral triangle without a base 4.Apply the same procedure to all the new straight lines(recursion). 5.Finally draw the lines.
- 7. Defining iterations Usually it is not feasible Step 4, in the last slide, a lot of times. We need to stop after a finite number of times. Each execution of step 1-3 is an iteration. The number of times we apply the rule is called the number of iterations.
- 8. The Koch Line Next we see the result of executing the steps. I used simple C graphics to make the fractals. The code is available on GitHub.
- 9. The Koch Line One Iteration:
- 10. The Koch Line Two Iterations:
- 11. The Koch Line Three Iterations:
- 12. The Koch Line Four Iterations:
- 13. The Koch Snowflake The Koch Line procedure could be used to make a Koch Snowflake To make a Koch Snowflake: 1.Make an equlateral trinangle 2.Apply Koch Line procedure to all the sides of the triangle Let's see what the resulting fractal looks like.
- 15. The Koch Snowflake In different colours
- 16. One More Example: The Sierpinski Arrowhead Curve
- 17. The Sierpinski Arrowhead Curve Following are the steps to make a sierpinski arrowhead curve 1. Draw an imaginary line. Think of it as a base of an equilateral triangle. 2. Move up (while drawing) one side. Stop halfway. 3. Move parallel to base till you reach the other side. 4. Move down the side to the base line. 5. Apply same procedure to all lines( Recursion ). The triangles on slanting lines must point inwards. The triangle on the horizontal line must point outwards.
- 18. The Sierpinski Arrowhead Curve One Iteraton:
- 19. The Sierpinski Arrowhead Curve Two Iteratons:
- 20. The Sierpinski Arrowhead Curve Three Iteratons:
- 21. The Sierpinski Arrowhead Curve Four and Five iterations skipped..
- 22. The Sierpinski Arrowhead Curve Six iterations:
- 23. The Sierpinski Arrowhead Curve In different colours:
- 24. Conclusions
- 25. Things to Note About Fractals The final structure is completely different form what we started with. Each smaller part is completely identical to the bigger part.
- 26. Recursion in Simple Language Recursion mainly consists of following two steps: 1.Apply some procedure to a thing. 2.Start from Step 1 for all smaller parts. In practice, we stop when we meet a base case.
- 29. Copper Crystals
- 30. Applications of recursion in Programming
- 31. Quick Sort algorithm quicksort(A, lo, hi) is if lo < hi then p := partition(A, lo, hi) quicksort(A, lo, p - 1) quicksort(A, p + 1, hi) Recursive Calls
- 32. Merge Sort function merge_sort(list m) // Base case. A list of zero or one elements is sorted, by definition. if m is empty then return m // Recursive case. First, divide the list into equal-sized sublists // consisting of the even and odd-indexed elements. //omitted // RECURSIVELY sort both sublists. left := merge_sort(left) right := merge_sort(right) // Then merge the now-sorted sublists. return merge(left, right)
- 33. Tower of Hanoi function hanoi is: input: integer n, such that n >= 1 1. if n is 1 then return 1 2. return [2 * [call hanoi(n-1)] + 1] end hanoi Interestingly, graphical representation of tower of hanoi is similar to that of sierpinski arrowhead curve Recursive Call
- 34. Useful Resources Original blog post Code Used to make fractals Snowflakes Fractals in Nature Wolfram Fractals Reference App Think Python book
- 35. Thank You Check out my blog for interesting new posts: singhcodes.wordpress.com Follow me on twitter: @gurpalsingh204