Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Problem-solving Strategies 2: Recursion

Description

This lecture covers strategies for problem-solving, including recursion and divide and conquer methods. It explains how to efficiently find misplaced elements in a list, the concept of dividing and grouping data to solve simpler sub-problems, and the recursive approach to problem-solving. Examples such as the Towers of Hanoi and calculating the sum of integers are discussed.

Official source

Related concepts (24)

Recursion (computer science)

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science. The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement.

Recursion

Recursion occurs when the definition of a concept or process depends on a simpler version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition. While this apparently defines an infinite number of instances (function values), it is often done in such a way that no infinite loop or infinite chain of references can occur.

Course-of-values recursion

In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion. In a definition of a function f by course-of-values recursion, the value of f(n) is computed from the sequence . The fact that such definitions can be converted into definitions using a simpler form of recursion is often used to prove that functions defined by course-of-values recursion are primitive recursive.

Divide-and-conquer algorithm

In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as sorting (e.g., quicksort, merge sort), multiplying large numbers (e.

Dynamic loading

Dynamic loading is a mechanism by which a computer program can, at run time, load a library (or other ) into memory, retrieve the addresses of functions and variables contained in the library, execute those functions or access those variables, and unload the library from memory. It is one of the 3 mechanisms by which a computer program can use some other software; the other two are static linking and dynamic linking.

Related lectures (20)

Algorithm Design: Divide and Conquer

Covers recursion, dynamic programming, and algorithm design using divide and conquer strategies.

Problem Solving Strategies: General Overview

Presents methods for problem-solving, emphasizing 'Divide and Conquer', recursion, and dynamic programming.

Recursive Algorithms: Divide and Conquer

Explores the concept of divide and conquer in recursive algorithms, exemplified by the Towers of Hanoi.

Dynamic Programming: Binomial Coefficients

Explores dynamic programming through binomial coefficients calculation, emphasizing efficiency and memoization in problem-solving.

Designing Algorithms: Recursion and Dynamic Programming