Алгоритмы на Python 3. Лекция №7

Name: Алгоритмы на Python 3. Лекция №7
Uploaded: 2017-11-22T05:42:40.000Z
Duration: 2 h 40 min 31 s

Lecture on Recursion

Introduction to the Topic

The lecture begins with an overview of the session, indicating that half of the students have already completed a test, while the other half will do so today. The topic for discussion is recursion.

Understanding Recursion through Russian Folktales

Recursion is introduced as a concept closely related to Russian mentality, illustrated through traditional tales like "The Turnip." This tale serves as a foundation for understanding recursion in programming.

The Story of "The Turnip"

In "The Turnip," the main character is a turnip that grows large and becomes difficult to pull out. This scenario sets up a recursive problem where each character calls upon another for help.

The grandfather attempts to pull out the turnip but fails due to insufficient strength (100 Newtons). He represents a function that cannot complete its task without additional input.

Delegation in Recursive Calls

To solve his problem, the grandfather calls upon his wife (the grandmother), asking her for 100 Newtons. She also struggles, providing only 50 Newtons.

The grandmother then calls their granddaughter for assistance, who can provide only 30 Newtons. Each character's inability to meet the required force illustrates how functions may call others when they cannot fulfill their tasks directly.

Further Delegation and Complexity

The granddaughter enlists help from a dog (the dog can provide 10 Newtons), who in turn calls upon a cat (with only 9 Newtons). This chain continues until it reaches the mouse, who can finally exert enough force alone.

The mouse does not call anyone else; it represents an endpoint or base case in recursion where no further delegation is needed.

Call Stack and Recursive Depth

As characters wait for results from one another, this reflects how functions operate within a call stack—waiting for responses before proceeding.

If any character had called even more helpers unnecessarily, it would illustrate poorly constructed recursion leading to excessive complexity without solving the original problem effectively.

Importance of Simplifying Subproblems

A critical aspect of effective recursion is ensuring that each subproblem must be simpler than its parent problem. This principle ensures progress towards reaching a base case efficiently.

Dynamic Programming vs. Recursion

While discussing recursion's structure, it's noted that dynamic programming addresses similar problems differently by storing results rather than recalculating them repeatedly.

Crafting Matryoshka Dolls: Another Example of Recursion

Overview of Matryoshka Doll Production

Transitioning from folktales to practical applications, matryoshka doll production exemplifies recursive processes where tasks are nested within one another based on levels of complexity.

Task Delegation in Doll Making

A master craftsman receives an external request to create dolls with five layers. He starts by making both top and bottom parts while delegating inner layers' creation downwards through successive craftsmen until reaching individual components at level one.

Understanding Recursion and Its Applications

Introduction to the Problem

The speaker introduces a task involving creating a nested structure (matryoshka dolls), simplifying the problem into manageable parts.

The process involves recursion, where the function must integrate results from previous calls, indicating that tasks can be broken down further.

Recursive Function Mechanics

As recursion unfolds, each function call retains its context while waiting for results from deeper calls, emphasizing the importance of managing state within recursive functions.

The speaker notes that functions can call themselves with the same name, illustrating how recursion works but warns against infinite loops without proper base cases.

Key Concepts in Recursion

A critical point is made about stack overflow risks when a function calls itself indefinitely; this highlights the need for defining both base and recursive cases clearly.

Two essential components of recursion are identified: establishing a base case to terminate recursion and defining how to reduce complexity through subproblems.

Practical Considerations

The speaker discusses scenarios where recursion may not be necessary or optimal, such as repetitive tasks better suited for iterative solutions.

An example is given comparing cyclical processes (like machining operations) with recursive approaches, suggesting that some problems are inherently iterative rather than recursive.

Implementing Recursion: Matryoshka Example

The discussion transitions to implementing a recursive function for generating matryoshka dolls, emphasizing clarity in defining parameters and conditions.

The speaker outlines steps for coding the matryoshka function, stressing checking for edge cases first before proceeding with further logic.

Coding Logic Breakdown

A detailed explanation follows on how to structure the code: starting with checking if n equals one (the simplest case).

If n is greater than one, it recursively calls itself with decremented values until reaching the base case. This illustrates practical application of previously discussed concepts in real coding scenarios.

Function Calls and Recursion in Programming

Understanding Function Calls with Nested Levels

The discussion begins with a function called "matreshka" being invoked at a nesting level of 5, illustrating how different levels of functions operate sequentially.

Each function call retains its own namespace, meaning that variables within each instance are unique to that specific invocation, even if they reference the same object.

When a function is called, it creates a new variable pointing to an object passed as an argument; this can lead to multiple instances referencing the same underlying data structure.

The Nature of Function Execution

A distinction is made between a function existing as static code (like an executable file on disk) and its execution as a dynamic computational process when called.

Multiple calls to the same function can create several active computational processes, each maintaining its own set of variable names until completion or termination.

Lifespan of Variables in Function Calls

Variables created during a function's execution exist only for the duration of that call; once completed without returning values, these variables cease to exist.

The analogy of "masters" is used to describe how each nested function operates independently while still being part of the overarching recursive process.

Visualizing Recursive Functions

An illustration involving cutting segments from shapes helps explain recursion visually; points are defined along segments based on ratios (e.g., alpha).

The goal is to draw nested squares recursively, where each square contains another smaller square inside it, demonstrating fractal-like behavior.

Managing Recursion Depth

To prevent infinite recursion and manage depth effectively, parameters must be added to control how deep the recursion goes.

The concept of recursion depth refers to the number of times functions are called within themselves; tracking this allows for better understanding and management during execution.

Drawing Rectangles and Fractals in Python

Introduction to Rectangle Drawing

The speaker discusses the convention of writing function names in lowercase, emphasizing the need for clarity when drawing shapes like rectangles.

To draw a rectangle, points A, B, C, and D are defined as tuples containing coordinates. This sets the foundation for constructing lines between these points.

Setting Parameters for Depth

The concept of "depth" is introduced, which refers to how many iterations or levels of detail will be drawn. A default value of 10 is suggested.

If the depth is less than 1 (i.e., zero), no rectangles will be drawn; thus, the function exits early without further processing.

Creating Lines and Points

The speaker mentions creating an object that represents a line but notes a temporary loss of focus on this aspect.

Two values from a tuple are extracted using unpacking syntax. This allows for easy access to x and y coordinates needed for drawing.

Utilizing Function Parameters Efficiently

The use of unpacking with tuples simplifies passing parameters into functions that require multiple arguments.

Unpacking can also apply to lists or tuples with more than two elements, showcasing Python's flexibility in handling function arguments efficiently.

Drawing Rectangles Using Loops

The speaker proposes using loops to avoid repetitive code when drawing multiple lines between points A-B, B-C, C-D, and D-A.

An elegant solution involves iterating through pairs of points using a loop structure that enhances code readability and efficiency.

Calculating New Points for Fractals

After drawing external squares (rectangles), new points must be calculated for recursive fractal drawing.

The process involves calling the fractal rectangle function recursively with adjusted parameters based on current depth minus one.

This structured approach highlights key programming concepts related to graphics in Python while providing clear references to specific moments in the transcript for further exploration.

Calculating Points in Vector Geometry

Understanding Point Calculations

The discussion begins with calculating specific points (1b, 1c, 1d) derived from a variable 'a', emphasizing the importance of understanding vector geometry.

The formula for point 1x is introduced: it combines coordinates from points A and B based on their respective proportions influenced by alpha.

Alpha is defined as a global constant (0.215), which plays a crucial role in determining the coordinates of point x.

Recursive Function Calls

The speaker notes that while calculating y-coordinates follows a similar method to x-coordinates, the complexity increases due to geometric considerations.

Geometric points are calculated and passed into a recursive function call, indicating an iterative approach to solving the problem.

Fractal Rectangle Generation

Setting Up Initial Parameters

The speaker initiates the fractal rectangle generation process by defining starting points at specified pixel values (e.g., 100 pixels).

Additional parameters are set for further calculations, including dimensions for height and width.

Adjusting Visual Parameters

Adjustments are made to the graphical window size to enhance visibility during demonstrations.

The speaker discusses manipulating parameters like alpha and recursion depth to explore different visual outcomes in fractal generation.

Exploring Recursion through Mathematical Examples

Introduction to Factorials

Transitioning from graphics back to mathematics, classic examples such as factorial calculations are introduced as foundational concepts of recursion.

Defining Recursive Cases

Emphasis is placed on understanding both base cases and recursive cases when discussing factorial functions.

A mathematical relationship is established: n! = n * (n - 1)! This analogy likens factorial calculation to nesting dolls.

Programming Factorial Functions

Formulating Recursive Functions

The speaker outlines how to define a factorial function programmatically, introducing notation for clarity in coding practices.

Handling Edge Cases

Discussion includes handling edge cases such as negative inputs where appropriate error handling should be implemented within the function logic.

This structured summary captures key insights from the transcript while providing timestamps for easy reference.

Understanding Factorials and Recursive Functions

The Nature of Factorials

The discussion begins with the concept of factorials, emphasizing that the function is defined for non-negative integers. The speaker notes that calling this function with negative numbers leads to issues.

Acknowledgment of potential pitfalls in defining conditions for factorial calculations, particularly when dealing with edge cases like zero or one.

The mathematical reasoning behind calculating the factorial of zero is explained; it involves multiplying by one, which simplifies computations.

Handling Negative Inputs

The speaker warns against invoking the factorial function with negative inputs, as it would lead to infinite recursion without a base case.

An assertion is proposed to prevent negative values from being processed, highlighting that factorial for negative numbers is not defined.

Implementing Assertions

An assertion statement is introduced to ensure that input values are non-negative. If an invalid value is passed, an error will be generated.

Emphasis on the importance of checking input validity before proceeding with calculations to avoid runtime errors.

Base Case and Recursive Calls

When n equals zero, the function immediately returns one as a known result without further computation. This serves as a base case for recursion.

Explanation of how recursive calls work: if n does not equal zero, the function calls itself with n - 1, illustrating how recursion unfolds step-by-step.

Recursion Mechanics

Clarification on direct versus indirect recursion; actions taken before diving deeper into recursive calls are highlighted as crucial steps in computation.

Upon returning from deeper recursive levels, additional operations (like multiplication by n) are performed before finalizing results.

Introduction to Euclidean Algorithm

Concept Overview

Transitioning from factorial discussions to introducing the Euclidean algorithm for finding the greatest common divisor (GCD).

Mathematical Foundations

The speaker outlines that given two integers a and b, they aim to find a segment length that can measure both evenly—this relates directly to GCD concepts.

Methodology Explanation

Initial thoughts on using subtraction (i.e., a - b) as part of determining GCD are shared. It’s noted that this difference also shares divisibility properties related to GCD.

Understanding the Euclidean Algorithm for GCD

Introduction to GCD Calculation

The speaker discusses how any number can be divided by its greatest common divisor (GCD), suggesting that one can replace a larger number with a smaller one in calculations.

If two numbers a and b are equal, then they represent the GCD. The process involves continuously reducing the size of a until reaching the GCD.

Recursive Definition of GCD

The speaker introduces a formal definition of the function gcd(a, b) without delving into edge cases initially, focusing on basic principles.

It is noted that if a = b, then gcd(a, b) equals either a or b. If not equal, two recursive cases arise based on which number is larger.

Implementation of Euclidean Algorithm

The classic algorithm involves calculating gcd(a - b, b) when a > b. This method is simple but requires careful implementation.

A conditional structure (if-else) is used to handle different scenarios based on whether a is greater than or less than b.

Handling Edge Cases and Comments

The speaker emphasizes clarity in code through comments and checks to ensure assumptions about variable sizes hold true during execution.

A "ghost" assertion may be used in programming to express confidence about certain conditions being met within the code.

Functional Programming Considerations

The discussion highlights that this version of the Euclidean algorithm suits functional programming languages where variables are immutable once assigned.

In contrast to imperative languages like Python, where variable reassignment is possible, functional languages require a different approach.

Optimizing the Algorithm

An optimization suggestion involves using modulo operation instead of subtraction for efficiency: gcd(a % b, b) reduces computational steps significantly.

If at any point a mod b = 0, it indicates that b itself is the GCD. This leads to an important adjustment in handling edge cases.

Final Thoughts on Implementation

The speaker explains how swapping values ensures consistent behavior regardless of input order; thus maintaining clarity in recursive calls.

By ensuring proper ordering before recursion begins, unnecessary complexity can be avoided while still achieving accurate results efficiently.

GCD and Recursive Functions

Understanding GCD through Recursion

The speaker discusses a higher level of recursion, simplifying the problem by removing two sub-cases, leading to a single case where they define gcd in terms of b and a % b.

They emphasize that if b equals zero, the result is straightforwardly zero, eliminating unnecessary complexity in the function.

A recursive definition for GCD is introduced: gcd(a, b) can be expressed as returning gcd(b, a % b) when b is not zero.

The speaker highlights the functional programming style used in this approach, which allows for clear and readable code while ensuring only one condition is evaluated at a time.

Transitioning to Exponentiation

The discussion shifts towards exponentiation using recursion. The speaker plans to reformulate traditional exponentiation into a recursive format.

They explain that exponentiation involves multiplying base a repeatedly for n times and consider how this can be implemented with loops versus recursion.

Recursive Power Function

Formulating the Power Function

The speaker introduces a recursive thought process for calculating powers: defining power as a^(n - 1) times a, reducing the problem size with each call.

They clarify that this method applies strictly to positive integers; negative or non-integer exponents complicate matters significantly.

Implementation Details

A function named power_up_all is proposed to encapsulate this logic. It will handle edge cases like when n = 0.

Two main cases are outlined: if n = 0, return 1; otherwise compute recursively as power(a, n - 1) times a.

Optimizing Exponentiation

Handling Edge Cases

The implementation begins with checking if n = 0, returning 1 immediately without further calculations.

Efficient Calculation Techniques

For large values of n, such as 1000, they note that naive recursion would be inefficient. Instead, they introduce an optimization technique based on whether n is even or odd.

Even vs Odd Exponents

Reducing Complexity

When dealing with even exponents (e.g., writing it as 2k), they suggest transforming it into (a^2)^k, effectively halving the exponent with each operation.

Final Thoughts on Efficiency

This method drastically reduces computation time by leveraging properties of exponents—every second reduction leads to an even number which simplifies calculations further.

This structured overview captures key concepts from the transcript while providing timestamps for easy reference.

Modifying Functionality in Code

Enhancing Efficiency in Calculations

The speaker discusses modifying a function to ensure faster calculations, emphasizing the importance of avoiding delays in processing.

A check is introduced to confirm that a number m is even before proceeding with certain operations, highlighting the need for conditional logic in programming.

The speaker explains how different cases are handled based on whether n (the input number) is odd or even, showcasing the use of conditional statements like elif.

The efficiency of exponentiation is discussed, noting that the number of multiplications required grows logarithmically rather than linearly with respect to n .

An example illustrates how reducing the exponentiation process can significantly decrease computation time, especially for large numbers.

Understanding the Tower of Hanoi Problem

Introduction to a Classic Puzzle

The speaker introduces the Tower of Hanoi as a mathematical puzzle and relates it to physical objects sold in stores, making it relatable.

Rules for moving disks (or "blinchiki") are outlined: only one disk can be moved at a time and larger disks cannot be placed on smaller ones.

The concept of using an auxiliary peg as temporary storage during moves is explained, adding complexity to the problem-solving approach.

Recursive Solution Approach

A recursive strategy is proposed where solving smaller subproblems leads to solving larger ones; starting from moving one disk up to multiple disks.

Visualizing the problem involves representing disks stacked on pegs and understanding their arrangement through recursion.

Implementation Details

The speaker emphasizes calculating which peg serves as temporary storage based on current positions, demonstrating logical reasoning in programming.

A systematic approach is described for transferring disks between pegs while maintaining order and adhering to rules established earlier.

Final steps involve moving back smaller pyramids after placing larger disks correctly, illustrating how recursion simplifies complex tasks into manageable parts.