.. This file is part of the OpenDSA eTextbook project. See .. http://opendsa.org for more details. .. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and .. distributed under an MIT open source license. .. avmetadata:: :author: Molly Domino Recursion ========= Objectives ---------- Upon completion of this module, students will be able to: * Trace recursive methods * Implement recursive methods * Consider the efficiency of recursive methods Suggested Reading ~~~~~~~~~~~~~~~~~ Chapter 7 from `Data Structures and Abstractions with Java, 4th edition by Frank M. Carrano and Timothy Henry `_ .. _RecursionIntro: Introduction to Recursion ------------------------- Intro to Recursion, Part 1 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. raw:: html

Intro to Recursion, Part 2 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

RecursionIntro.pdf .. raw:: html

Checkpoint 1 ------------ .. avembed:: Exercises/SWDesignAndDataStructs/RecursionCheckpoint1Summ.html ka :long_name: Checkpoint 1 .. _RecursionExample: Interactive: More Recursion : Factorial Examples -------------------------------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

RecursionExample.pdf .. raw:: html

Programming Practice: Recursion 1 --------------------------------- .. extrtoolembed:: 'Programming Practice: Recursion 1' :workout_id: 1916 .. _RecursionArray: Interactive: Recursion on Arrays: Display an Array ---------------------------------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

DisplayArrays.pdf .. admonition:: Correction to note! The code in the second example in this video is missing the ``{}`` in the ``if`` block. It should be: .. code-block:: java public static void displayArray2(int[] array, int first, int last) { if (first <= last) { displayArray2(array, first, last - 1); System.out.print(array[last] + " "); } } .. raw:: html

Checkpoint 2 ------------ .. avembed:: Exercises/SWDesignAndDataStructs/RecursionCheckpoint2Summ.html ka :long_name: Checkpoint 2 Interactive: Recursion on Arrays: Display the Middle of an Array ----------------------------------------------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

DisplayArraysMiddle.pdf .. raw:: html

Checkpoint 3 ------------ .. avembed:: Exercises/SWDesignAndDataStructs/RecursionCheckpoint3Summ.html ka :long_name: Checkpoint 3 Programming Practice: Recursion 2 --------------------------------- .. extrtoolembed:: 'Programming Practice: Recursion 2' :workout_id: 1917 .. _RecursionChain: Interactive: Recursion on Linked Chains ---------------------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

DisplayBagsRecursively.pdf .. raw:: html

Interactive: Tower of Hanoi ----------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

TowersOfHanoi.pdf .. raw:: html

Checkpoint 4 ------------ .. avembed:: Exercises/SWDesignAndDataStructs/RecursionCheckpoint4Summ.html ka :long_name: Checkpoint 4 .. _RecursionConclusion: Interactive: Recursion Wrap Up ------------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

RecursionWrapUp.pdf .. raw:: html

Programming Practice: Recursion 3 --------------------------------- .. extrtoolembed:: 'Programming Practice: Recursion 3' :workout_id: 1918 Forward Flow Tracing Exercises ------------------------------ .. avembed:: Exercises/RecurTutor/RecTraceSummFwdFlow.html ka :long_name: Recursion Tracing Exercises Set 1 Backward Flow Tracing Exercises ------------------------------- .. avembed:: Exercises/RecurTutor/RecTraceSummbckwrdFlow.html ka :long_name: Recursion Tracing Exercises Set 2 Find Error Tracing Exercises ---------------------------- .. avembed:: Exercises/RecurTutor/RecTraceSummFuncErr.html ka :long_name: Recursion Tracing Exercises Set 3 Two Recursive Calls Tracing Exercises ------------------------------------- .. avembed:: Exercises/RecurTutor/RecTraceSummTwoRC.html ka :long_name: Recursion Tracing Exercises Set 4 How Many Times Tracing Exercises -------------------------------- .. avembed:: Exercises/RecurTutor/RecTraceSummHowmany.html ka :long_name: Recursion Tracing Exercises Set 5 Harder Tracing Exercises ------------------------ .. avembed:: Exercises/RecurTutor/RecTraceSummHard.html ka :long_name: Recursion Tracing Exercises Set 6