Back To Course

Computer Science 113: Programming in Python10 chapters | 53 lessons

Instructor:
*Apostolos Ntokos*

Apostolos has a master degree in Computer Science and his academic interests are: Algorithms, Machine Learning, Game Theory.

In this lesson, we will learn about Recursive Algorithms and their benefits and challenges. We will explain all this using the Divide and Conquer Algorithm, which is a typical example of the recursive technique. We will explain how to code recursive functions in Python, how to form recurrence relations, how to use the Master Theorem, as well as write a function that performs a recursive search of data (Binary Search).

A recursive algorithm is an algorithm which calls itself with a **smaller** problem. More generally, if a problem can be solved utilizing solutions to smaller versions of the same problem and the smaller versions reduce to easily solvable cases, then one can use a recursive algorithm to solve that problem.

When we design and implement a recursive algorithm, we use the **Divide and Conquer** algorithmic technique. Like greedy and dynamic programming, Divide and Conquer is one of the most important and widely used algorithmic paradigms. The general method of designing Recursive Algorithms is the following:

**Divide:**Divide the given problem into 'smaller' and 'simpler' sub-problems of the same type.**Conquer:**Recursively solve these sub-problems, using simple algorithms usually in constant time.**Combine:**Combine the answers of the sub-problems, to produce the solution of the initial problem.

Each recursive algorithm must have:

**Base case:**A case for which the answer is known (and can be expressed without recursion).**General (recursive) case:**The case for which the solution is expressed in terms of a smaller version of itself.

Next, we implement, as an example, a simple recursive algorithm for computing the k-th power of 2.

def kPowerOf2(k):

if k == 0:

return 1

else:

return 2*kPowerOf2(k-1)

print(kPowerOf2(5))

Here, the base case is the case where k is equal to 0, otherwise we are in the general case.

Each time kPowerOf2() is called, Python instantiates a data structure to represent that particular call to the function. This data structure is called a stack frame. When the function returns, the return value is left on top of the stack for the calling function to access.

Recurrence relations give us a powerful tool for calculating the time complexity of Recursive Algorithms. It is very important to compute the time complexity of a recursive algorithm, because as we will see sometimes the time complexity could be exponential, which means that we have to change our implementation. But how do we form a recurrence relation?

Let's use, as an example, the Binary Search algorithm. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log n).

Let's implement the binary search in the Python programming language.

def binary_search(A, l, h, k):

if h >= l:

mid = l + (h - l)/2

if A[mid] == k:

return 'k is found'

elif A[mid] > k:

return binary_search(A, l, mid-1, k)

else:

return binary_search(A, mid+1, h, k)

else:

return 'k is not found'

As we can see, the binary search function takes 4 parameters (A, l, h, k):

**A**: the array**l**: the leftmost element of the array**h**: the rightmost element of the array**k**: the element we search for

An empty list is a base case for the binary search algorithm. We check this using the condition **if h >= l**. The binary search algorithm actually has another type of base case: If we find the element we are looking for in the middle of the list, we are done. There is no need for further recursion.

Now, let's form the recurrence relation. In each step, the algorithm:

- compares the input element k with the value of the middle element in array. If the values match, return the index of middle.
**O(1)** - otherwise, if k is less than the middle element, then the algorithm recurs with left side of middle element, else it recurs with the right side of middle element. So, in each step, we discard half of the array.
**T(n/2)**

The algorithm solves the problem recursively solving one sub-problem of size n/2. So, the recurrence relation is: **T(n) = T(n/2) + O(1)**.

In order to solve a recurrence relation we can apply the Master Theorem.

Figure 1 outlines the definition of the Master Theorem.

Parameter **a** denotes the number of sub-problems, parameter **b** is the size of each problem's sub-array, and **f(n)** is the time taken to create the sub-problems and combine the solutions.

Now let's apply the Master Theorem to the recurrence relation of the Binary Search.

**T(n) = T(n/2) + O(1)**, so:

- a = 1 , b = 2.
- O(1) = Theta(n^0) = Theta(1)

So, **T(n) = Theta(n^0 log n) = Theta(log n)**.

The time complexity of the Binary Search is O(log n), which is 'faster' than the time complexity of the linear search O(n). In this case, the Divide and Conquer technique helped us to solve a problem more efficiently in terms of time complexity.

**Note:** If we cannot use the Master Theorem, we can solve the recurrence relation using the recursive tree, or mathematical induction.

As we saw, the divide and conquer technique helped us to solve a problem more efficiently. Now, a question arises: Does this technique always help us to solve a problem efficiently?

To answer this question we will examine the Fibonacci numbers. The Fibonacci numbers are the numbers in the following integer sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,... . In mathematical terms, the sequence F(n) of Fibonacci numbers is defined by the recurrence relation: **F(n) = F(n-1) + F(n-2)**, with seed values **F(0) = 0**, ** F(1) = 1**.

Next, we implement a Fibonacci number calculator, using the Divide and Conquer technique, in the Python programming language.

def fibonacci(n):

if n < 0:

print('ERROR: Negative number')

elif n == 0:

return 0

elif n == 1:

return 1

else:

return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(4))

Solving the recurrence relation: **F(n) = F(n-1) + F(n-2)** tell us that the time complexity is exponential. We can understand this, by looking at the recursive tree (Figure 2).

We can observe that the Divide and Conquer technique, in his case, does a lot of repeated work. For example, it recalculates the fib(4), 3 times and fib(3), 5 times, and so on.

To avoid these recalculations, we have to store the Fibonacci numbers calculated so far. (Fibonacci Dynamic Programming).

In this lesson, we have seen how Divide and Conquer (Recursive algorithms) technique is defined. We presented the general method of designing Recursive Algorithms which consists of three steps:

**Divide:**Divide the given problem into 'smaller' and 'simpler' sub-problems of same type.**Conquer:**Recursively solve these sub-problems, using simple algorithms usually in constant time.**Combine:**Combine the answers of the sub-problems, to produce the solution of the initial problem.

Furthermore, we have seen how to form a recurrence relation and how to apply the Master Theorem to compute the time complexity of a recursive algorithm. As an example, we used the Binary Search Algorithm.

Finally, we have seen that the Divide and Conquer technique does not always help us to solve problems efficiently. As an example we used the calculation of Fibonacci numbers.

To unlock this lesson you must be a Study.com Member.

Create your account

Are you a student or a teacher?

Already a member? Log In

BackWhat teachers are saying about Study.com

Already registered? Login here for access

Did you know… We have over 160 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

You are viewing lesson
Lesson
3 in chapter 10 of the course:

Back To Course

Computer Science 113: Programming in Python10 chapters | 53 lessons

- Computer Science 109: Introduction to Programming
- Introduction to HTML & CSS
- Introduction to JavaScript
- Computer Science 332: Cybersecurity Policies and Management
- Introduction to SQL
- Algorithmic Analysis, Sorting & Searching
- Computer Programming Basics
- Stacks & Queues for Data Structures
- Functions & Modules in Programming
- Built-In Data Types for Programming
- CEOE Test Cost
- PHR Exam Registration Information
- Claiming a Tax Deduction for Your Study.com Teacher Edition
- What is the PHR Exam?
- Anti-Bullying Survey Finds Teachers Lack the Support They Need
- What is the ASCP Exam?
- ASCPI vs ASCP

- Dorsiflexion vs. Plantar Flexion
- Process Synchronization in Operating Systems: Definition & Mechanisms
- Plastic: Types & Uses
- Decision Making: Skills & Techniques
- Graphics Library in Python: Definition & Examples
- Rainforest Project Ideas
- Basketball Shooting Lesson Plan for Elementary
- Quiz & Worksheet - Love in A Midsummer Night's Dream
- Quiz & Worksheet - Memory Partitioning Overview
- Quiz & Worksheet - Finding the Centroid of a Triangle
- Quiz & Worksheet - Understanding Scotomas
- Flashcards - Measurement & Experimental Design
- Flashcards - Stars & Celestial Bodies
- Cyberbullying Facts & Resources for Teachers
- Common Core English & Reading Worksheets & Printables

- Western Civilization from 1648 for Teachers: Professional Development
- Introduction to World Religions: Help and Review
- NY Regents Exam - Global History and Geography: Help and Review
- UExcel Psychology of Adulthood & Aging: Study Guide & Test Prep
- HiSET Language Arts - Reading: Prep and Practice
- TExES Life Science: Scientific Inquiry
- TExES Life Science: Scientific Inquiry
- Quiz & Worksheet - Leveling Texts
- Quiz & Worksheet - Motor Learning Instruction in Physical Education
- Quiz & Worksheet - Cytotoxic Hypersensitivity
- Quiz & Worksheet - Leading Virtual Teams
- Quiz & Worksheet - Characteristics of Cholera

- What is Cost Structure? - Definition, Types & Examples
- Aneurysm: Definition, Causes & Symptoms
- How to Prep for the NYS English Regents Exam
- What is Micro Credentialing?
- Measurement Games for Kids
- Hawaii Common Core Standards
- Georgia Common Core Performance Standards
- Study.com's Virtual Classrooms
- How to Transfer Your Study.com Credit
- Course Curriculum Template
- Writing Center Ideas for Preschool
- How to Prep for the NYS Physics Regents Exam

- Tech and Engineering - Videos
- Tech and Engineering - Quizzes
- Tech and Engineering - Questions & Answers

Browse by subject