Recursion

How is a recursive function made?

Base cases and recursive cases

How to write a recursive function?

What happens when a recursive function gets executed?

Call stack

What are base cases and recursive cases?

How to identify base cases and recursive cases?

Difference between a recursive function with one recursive call and with multiple recursive calls

Why do we need the recursion tree?

How to draw the recursion tree?

"ways to climb stairs" example

How to add some code to be able to visualize the call stack

Example on "merge sort"

How to add some code to be able to visualize the recursion tree

Example on "ways to climb stairs"

Introduction to time complexity analysis of recursive functions

How to analyze the time complexity of a recursive function by using the recursion tree

How to analyze the time complexity of a recursive function by using the recurrence relation (substitution method)

How to analyze the time complexity of a recursive function by using the Master theorem method

How to analyze the space complexity of a recursive function

The difference between iteration and recursion

When to choose iteration?

When to choose recursion?

How to transform a recursive function into an iterative one?

How to transform an iterative function into a recursive one?

What is memoization?

How does it work?

How to implement memoization?

How to optimize "ways to climb stairs" solution with memoization?

Process demonstration

Solution code

What is dynamic programming?

How does it work?

"Fibonacci nth term" example

How to optimize "ways to climb stairs" solution with dynamic programming?

Process demonstration

Solution code

What is divide-and-conquer?

"Merge sort" example

"Karatsuba algorithm" example

Decrease-and-conquer

What is backtracking?

"Combinations with valid weight" example

"N-queens" problem description

Solution explanation

Process demonstration on an example

Solution code

What is a recursive data type?

What is a linked list?

Traversal and searching example

What is a tree?

Recursive manipulations examples

What is a graph?

DFS traversal

What is tail recursion?

The benefit of using tail recursion

How to transform a non-tail-recursive function into a tail-recursive one

"Factorial" example

"Replace in array" example

"Sum to n" example

"a power b" example

"get minimum" example

"binary tree inorder traversal" example

"Fibonacci nth term" example

What is double recursion?

"Ackermann function" example

Understanding

Dividing the problem into sub-problems

Trusting the recursive process

Visualizing the recursive process

Practising

"Sum of digits" problem description

Solution explanation

Process demonstration on an example

Solution code

"Count occurrences" problem description

Solution explanation

Process demonstration on an example

Solution code

"Minimum cost path in matrix" problem description

Solution explanation

Process demonstration on an example

Solution code

"Has adjacent duplicates" problem description

Solution explanation

Process demonstration on an example

Solution code

"Reverse string" problem description

Solution explanation

Process demonstration on an example

Solution code

"All possible phrases" problem description

Solution explanation

Process demonstration on an example

Solution code

"Keypad combinations" problem description

Solution explanation

Process demonstration on an example

Solution code

"String subsequences" problem description

Solution explanation

Process demonstration on an example

Solution code

"Binary numbers with at most two zeros" problem description

Solution explanation

Process demonstration on an example

Solution code

"Word search" problem description

Solution explanation

Process demonstration on an example

Solution code

"Array permutations" problem description

Solution explanation

Process demonstration on an example

Solution code