Update Recursion.md

sinanazem · web-flow · commit 65c038ed75c8 · 2024-06-06T19:48:19.000+03:30
diff --git a/recursion/Recursion.md b/recursion/Recursion.md
@@ -1 +1,115 @@
 
+# Recursion in Python
+
+Recursion is a fundamental concept in computer science and programming where a function calls itself to solve smaller instances of the same problem. This README.md file provides an overview of recursion in Python, including its definition, common use cases, and examples.
+
+## Table of Contents
+- [What is Recursion?](#what-is-recursion)
+- [Base Case and Recursive Case](#base-case-and-recursive-case)
+- [Common Use Cases](#common-use-cases)
+- [Examples](#examples)
+  - [Factorial](#factorial)
+  - [Fibonacci Sequence](#fibonacci-sequence)
+  - [Sum of a List](#sum-of-a-list)
+  - [Binary Search](#binary-search)
+- [Advantages and Disadvantages](#advantages-and-disadvantages)
+- [Conclusion](#conclusion)
+
+## What is Recursion?
+
+Recursion occurs when a function calls itself as part of its execution. Each recursive call processes a smaller portion of the problem until a base case (termination condition) is met, which stops the recursion.
+
+## Base Case and Recursive Case
+
+A recursive function typically has two main components:
+1. **Base Case**: The condition under which the recursion ends. This prevents infinite recursion and eventual stack overflow.
+2. **Recursive Case**: The part of the function where the function calls itself with a smaller or simpler argument.
+
+## Common Use Cases
+
+Recursion is often used for problems that can be broken down into smaller, repetitive tasks. Common use cases include:
+- Mathematical computations (e.g., factorials, Fibonacci numbers)
+- Tree and graph traversals
+- Sorting algorithms (e.g., quicksort, mergesort)
+- Divide and conquer algorithms (e.g., binary search)
+
+## Examples
+
+### Factorial
+
+The factorial of a non-negative integer `n` is the product of all positive integers less than or equal to `n`.
+
+```python
+def factorial(n):
+    if n == 0:
+        return 1
+    else:
+        return n * factorial(n - 1)
+
+print(factorial(5))  # Output: 120
+```
+
+### Fibonacci Sequence
+
+The Fibonacci sequence is defined as follows: `F(0) = 0`, `F(1) = 1`, and `F(n) = F(n-1) + F(n-2)` for `n > 1`.
+
+```python
+def fibonacci(n):
+    if n <= 0:
+        return 0
+    elif n == 1:
+        return 1
+    else:
+        return fibonacci(n - 1) + fibonacci(n - 2)
+
+print(fibonacci(6))  # Output: 8
+```
+
+### Sum of a List
+
+Recursively summing the elements of a list.
+
+```python
+def sum_list(lst):
+    if not lst:
+        return 0
+    else:
+        return lst[0] + sum_list(lst[1:])
+
+print(sum_list([1, 2, 3, 4]))  # Output: 10
+```
+
+### Binary Search
+
+Binary search is a divide-and-conquer algorithm to find an element in a sorted list.
+
+```python
+def binary_search(arr, target, low, high):
+    if low > high:
+        return -1
+    mid = (low + high) // 2
+    if arr[mid] == target:
+        return mid
+    elif arr[mid] > target:
+        return binary_search(arr, target, low, mid - 1)
+    else:
+        return binary_search(arr, target, mid + 1, high)
+
+arr = [1, 2, 3, 4, 5, 6, 7]
+target = 4
+print(binary_search(arr, target, 0, len(arr) - 1))  # Output: 3
+```
+
+## Advantages and Disadvantages
+
+### Advantages
+- Simplifies code for problems that can be divided into similar sub-problems.
+- Often more intuitive and easier to implement for certain algorithms (e.g., tree traversals).
+
+### Disadvantages
+- Can lead to high memory usage and stack overflow if not implemented correctly.
+- Generally, less efficient due to overhead of multiple function calls.
+
+## Conclusion
+
+Recursion is a powerful tool in a programmer's toolkit. Understanding how to properly implement recursive functions in Python can help solve complex problems more elegantly and succinctly. However, it is important to be mindful of the base case to prevent infinite recursion and to consider the efficiency impact on your program.
