Recursion & Factorial in Programming

Recursion & Search

• Recursion: A technique for solving a complex problem by breaking it down into smaller, self-similar subproblems. The solution to the smaller problem is used to solve the larger problem.
• Recursion solves problems by repeatedly applying the same procedure to progressively smaller instances of the problem. This effectively reduces the overall problem into manageable steps.
• Recursion in programming: A function calling itself, either directly or indirectly.
• Recursion is a common concept in mathematics and programming.

Factorial

• Factorial(5): 5 * 4 * 3 * 2 * 1 = 120 - O(n)
• Iterative approach: A loop that calculates the factorial.
• Recursive approach: A function that calls itself to calculate the factorial.

Recursion Function Example

• Recursive functions have two main parts:
  • Base Case: A condition that stops the recursion. This prevents infinite loops. For factorial, n=1 or n=0
  • Recursive Step: The part of the function that calls itself with modified parameters. For factorial, it multiplies by (n-1) until the base case is met

Recursion & Iteration

• Iteration: Uses loops (e.g., for, while) to repeatedly execute a block of code until a condition is met.
• Comparing Recursion and Iteration:
  • Recursion can be elegant and easier to understand for certain problems, but can be less efficient than iteration due to function call overhead.
  • Iteration is generally more efficient since it avoids the function call overhead, but can sometimes make the code structure more complex.

Using Recursion in Binary Search

• Binary Search: A search algorithm that quickly locates a target value within a sorted array.
• This method repeatedly divides the search interval in half until the target value is found. This gives a time complexity of O(log n).

Why Learn Recursion

• "Cultural Experience": Recursion provides a unique way of thinking about problem-solving.
• Problem-Solving Efficiency: Recursion can solve problems more efficiently than iteration in some situations. Examples include: factorials, Fibonacci sequence, and tree traversal
• Elegant Code: When implemented correctly, recursion leads to concise and readable code.
• Functional Programming: Languages like Scheme, ML, and Haskell use recursion extensively.

The Idea of Recursion

• Breaking Down Problems: Recursion involves breaking a larger problem into smaller, self-similar subproblems, which can then be solved.
• Small Problem Instances: Finding a part of the problem that can easily be answered.
• Information from Neighbors: Consider how you would get help from a neighbor to solve the problem. This models the subproblem and the relationship to the original problem. An example is given by the image of a row of people, where individual people can be asked how many people are standing behind them.

Recursive Algorithm Example (People Counting)

• Ask people behind you for information
• If someone is behind you, request the number of people behind them
• The response from the person behind you is N, the answer for you is N+1
• If there are no people behind you, the answer is 0

How Recursive Functions Work

• External Call: A recursive function is called by some external code.
• Base Condition: If the base case is met, the function performs an action and returns.
• Recursively Calling: Otherwise, the function performs some required processing and calls itself to continue calculating the result.

Recursive Function Example (Factorial)

• Code example demonstrating recursion for factorial calculations

Fibonacci Function

• Defining the Fibonacci Sequence: Explanation of the sequence, using mathematical relationships to calculate each value.
• Recursive Calculation: Demonstrates recursion to implement the calculation.
• Iterative Calculation: Example of calculating the Fibonacci numbers with an iterative approach.

Searching Algorithms

• Searching: An operation that locates a specified element or value in a data structure.
• Successful or Unsuccessful: A search can be categorized as successful if the target value is found or unsuccessful otherwise.

Linear Search

• Definition: The simplest search algorithm. It sequentially checks each element in a list until the target value is found.
• Steps: Start from the first element, compare with the target, and repeat until the target is found or the end of the list is reached.

Linear Search Code Example

Binary Search

• Definition: A search algorithm that works on a sorted list. Repeatedly divides the list into half, to target a section of the array which may contain the target

Binary Search Steps

• Steps for using Binary Search: Starts with the full list, determines the midpoint, and continues to recursivelty narrow down the search interval

Binary Search Code Example

Advantages of Binary Search

• Speed: Notably faster than linear search for large arrays, due to dividing the search space in half.
• Complexity: More efficient than other similar algorithms—interpolation search or exponential search.
• External Memory: Is effective for searches on large datasets stored in external memory like hard drives or cloud storage.

Disadvantages of Binary Search

• Data Structure Requirements: Involves using a sorted list to function properly
• Memory Structure: Needs contiguously stored data
• Comparable Data Types: Algorithm requires elements with clear ordering or comparison capability.