WEBVTT

00:00.000 --> 00:08.000
Recursive Algorithms

00:08.000 --> 00:16.000
In this video, we will understand how recursion works and identify base and recursive cases.

00:16.000 --> 00:21.000
Write recursive methods to compute factorial and Fibonacci values.

00:21.000 --> 00:29.000
Evaluate the efficiency differences between recursive and iterative solutions.

00:29.000 --> 00:32.000
Introduction to recursion

00:32.000 --> 00:37.000
Recursion is a programming technique where a function calls itself to solve a problem.

00:37.000 --> 00:44.000
Instead of solving the problem all at once, recursion breaks the problem into smaller, similar subproblems.

00:44.000 --> 00:48.000
To work correctly, every recursive function must have two parts.

00:48.000 --> 00:55.000
A base case that stops the recursion and a recursive case that continues the process.

00:56.000 --> 01:01.000
In this lesson, we will apply recursion to calculate factorials and Fibonacci numbers

01:01.000 --> 01:07.000
and compare the efficiency of recursive and iterative solutions.

01:07.000 --> 01:11.000
Factorial using recursion

01:11.000 --> 01:17.000
The factorial of a number n is the product of all positive integers from n down to 1.

01:17.000 --> 01:21.000
For example, factorial of 5 equals 120.

01:21.000 --> 01:27.000
In recursive form, base case, factorial 0 equals 1.

01:27.000 --> 01:33.000
Recursive case, factorial n equals n times factorial n minus 1 1.

01:33.000 --> 01:37.000
Each call reduces n by 1 until it reaches 0.

01:37.000 --> 01:40.000
The results then return back through the call stack.

01:40.000 --> 01:47.000
The recursive factorial method has O of n time complexity and O of n space complexity.

01:47.000 --> 01:54.000
Because each call is stored in memory until the function returns.

01:54.000 --> 01:59.000
Fibonacci using recursion

01:59.000 --> 02:02.000
The Fibonacci sequence begins with 0 and 1.

02:02.000 --> 02:05.000
Each new number is the sum of the previous two.

02:05.000 --> 02:10.000
So, 5 0 equals 0, 5 1 equals 1.

02:10.000 --> 02:18.000
Fib n equals Fib n minus 1 plus Fib n minus 1 2, 4 n greater than 1.

02:18.000 --> 02:22.000
This recursive version makes two new calls for each non-base case.

02:22.000 --> 02:25.000
As n increases, the number of calls grows very quickly.

02:25.000 --> 02:30.000
The time complexity becomes O of 2 to the power of n,

02:30.000 --> 02:34.000
making naive recursive Fibonacci slow for larger values.

02:34.000 --> 02:42.000
To improve performance, we use iteration or memoization to store previously computed results.

02:42.000 --> 02:45.000
Efficiency and stack usage.

02:45.000 --> 02:51.000
Recursion uses the call stack, where each function call is stored until it completes.

02:51.000 --> 02:55.000
In factorial, the stack grows one step at a time.

02:55.000 --> 03:01.000
In Fibonacci, the stack grows rapidly because many values are recalculated.

03:01.000 --> 03:04.000
This is why recursive factorial is manageable,

03:04.000 --> 03:12.000
while naive recursive Fibonacci becomes inefficient.

03:12.000 --> 03:18.000
Recursion breaks a problem into smaller versions of itself and solves them step by step.

03:18.000 --> 03:21.000
The factorial example shows a straightforward recursive chain.

03:21.000 --> 03:25.000
While the Fibonacci example shows how recursion can become slow

03:25.000 --> 03:28.000
if the same values are recalculated many times.