> [!Cite]- Metadata > 2025-07-21 23:23 > Status: #concept #mathematics > Tags: `Read Time: 2m 29s` ### One-Sentence Summary > Recursion is a technique where a function or process refers back to itself, directly or indirectly, to solve a problem by reducing it to simpler versions, terminating at a well defined base case. --- ### Definition(s) and Key Terms - **Base case:** The simplest instance of the problem, which can be solved directly and stops further recursion. - **Recursive case:** The part of the definition or algorithm that reduces the problem to a simpler form, calling itself with updated parameters. - **Call stack:** The stack data structure used to keep track of recursive function calls. - **Termination:** The guarantee that the recursion eventually reaches the base case and halts. - **Direct recursion:** When a function calls itself directly. - **Indirect recursion:** When a function calls another function that eventually calls the first one. - **Single recursion:** Recursion involving one recursive call per invocation (e.g. factorial) - **Multiple recursion:** Recursion involving more than one self-reference per invocation (e.g., Fibonacci, tree traversal) --- ### Core Components or Principles - A clearly defined base case to end the recursive process - A recursive case that reduces the problem and makes a recursive call - Progress toward the base case in each recursive step, ensuring the solution does not enter infinite recursion. - State and context management with a call stack to keep track of return points. - Combining results from recursive calls to produce the final answer. --- ### Origins and Historical Context - The roots of recursion can be tracked to mathematical induction and recursive definitions in logic and early mathematics. - In computer science, recursion became formalized with the study of algorithms and computability in the 20th century, especially through work on recursive functions in logic and early programming languages. - Niklaus Wirth emphasized its power to define infinite sets or computations with finite, elegant statements. --- ### Interdisciplinary Connections - **Mathematics:** Recursive definitions of sequences (factorials, Fibonacci, fractals), mathematical induction. - **Computer Science:** Central to algorithm design, data structures (trees, graphs), functional programming - **Linguistics:** Grammar and syntax rules with self-referential structures (recursive grammar constructs). - **Philosophy & Logic:** Self-reference, definitions, and paradoxes (e.g., Russell's paradox) - **Physics & Biology:** Recursive processes in fractal geometry, branching systems in nature. --- ### Critiques and Debates - **Efficiency concerns:** Recursive solutions can be less efficient than iterative ones, due to call stack usage and possible exponential growth in multiple recursion. - **Readability and debugging:** Deep or complex recursion can lead to stack overflows or be challenging to understand and maintain. - **Replaceability:** For some problems, iterative approaches are clearer or more practical, leading to debates over when recursion is most appropriate. --- ### Applications of recursion - **Sorting algorithms:** Quicksort, mergesort - **Searching algorithms:** Binary search, tree traversal - **Mathematical computations:** Factorials, Fibonacci numbers, power functions - **Structural definitions:** File system, XML, and organizational trees. - **Problem decomposition:** Tower of Hanoi, combinatorial enumeration. [[[3]]] ### Case Studies - **Factorial function:** Defined recursively so that n!=n×(n−1)!n!=n×(n−1)! with base case 0!=10!=1 - **Fibonacci sequence:** Each number defined as the sum of the two preceding ones, with base cases F(0)=0F(0)=0, F(1)=1F(1)=1 - **Tree Traversal:** Visiting all nodes in a tree structure using recursive algorithms (preorder, inorder, postorder) - **Sorting:** Quicksort and mergesort algorithms use recursion for breaking down lists into smaller partitions or merges - **Tower of Hanoi:** Classic puzzle solved efficiently through recursive decomposition. --- ### Insights & Reflections - What surprised me? - How does this reshape my thinking? - What new questions arise from this? --- ### **Resources** [Recursion (computer science) - Wikipedia](https://en.wikipedia.org/wiki/Recursion_\(computer_science\)) [Introduction to Recursion - GeeksforGeeks](https://www.geeksforgeeks.org/dsa/introduction-to-recursion-2/) [Recursion in Programming: What is it?](https://www.codecademy.com/resources/blog/recursion) [computer science - What is recursion and when should I use it? - Stack Overflow](https://stackoverflow.com/questions/3021/what-is-recursion-and-when-should-i-use-it) [What is Recursion? : r/C_Programming](https://www.reddit.com/r/C_Programming/comments/1aw0rcx/what_is_recursion/) [Programming - Recursion](https://users.cs.utah.edu/~germain/PPS/Topics/recursion.html) [5.2. Recursion — Discrete Structures for Computing](https://www.csd.uwo.ca/~abrandt5/teaching/DiscreteStructures/Chapter5/recursion.html)