title

Introduction to Recursion (Data Structures & Algorithms #6)

description

Recursion explained. Java & Python sample code below.
Check out Brilliant.org (https://brilliant.org/CSDojo/), a website for learning math and computer science concepts through solving problems. First 200 subscribers will get 20% off through the link above.
Special thanks to Brilliant for sponsoring this video.
Find sample code in Python and Java here: https://www.csdojo.io/recursion
This was #6 of my data structures & algorithms series. You can find the entire series in a playlist here: https://goo.gl/wy3CWF
You can check out my video about dynamic programming here: https://youtu.be/vYquumk4nWw
Also, keep in touch on Facebook: https://www.facebook.com/entercsdojo
If you want to find my introduction to recursion, you can check it out here: https://youtu.be/B0NtAFf4bvU

detail

{'title': 'Introduction to Recursion (Data Structures & Algorithms #6)', 'heatmap': [{'end': 752.456, 'start': 719.437, 'weight': 0.808}, {'end': 1238.219, 'start': 1194.185, 'weight': 0.893}], 'summary': 'Introduces recursion by explaining factorials and their definition, demonstrating the calculation of 3 factorial as 6. it also discusses the implementation of a recursive factorial function in java, the fibonacci sequence, and its recursive solution, and explores recursion in the fibonacci function with examples of frog jumping problems.', 'chapters': [{'end': 357.367, 'segs': [{'end': 34.821, 'src': 'embed', 'start': 0.269, 'weight': 2, 'content': [{'end': 4.171, 'text': "Hey everyone, in this video, I'm going to give you an introduction to recursion.", 'start': 0.269, 'duration': 3.902}, {'end': 11.694, 'text': 'So in computer science, recursion is a way of solving a problem by having a function called itself.', 'start': 4.911, 'duration': 6.783}, {'end': 16.015, 'text': "To see how that works exactly, let's take a look at a few examples here.", 'start': 12.554, 'duration': 3.461}, {'end': 21.177, 'text': "First of all, let's think about factorials and let's just quickly review factorials here.", 'start': 16.676, 'duration': 4.501}, {'end': 34.821, 'text': "If you're given a positive integer n, n factorial is equal to n times n minus one times n minus two times and so on down to three times two times one.", 'start': 21.797, 'duration': 13.024}], 'summary': 'Introduction to recursion in computer science, explained with factorial example.', 'duration': 34.552, 'max_score': 0.269, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU269.jpg'}, {'end': 261.728, 'src': 'embed', 'start': 187.569, 'weight': 0, 'content': [{'end': 190.952, 'text': 'zero factorial is equal to zero.', 'start': 187.569, 'duration': 3.383}, {'end': 199.562, 'text': 'here, right here times zero, minus one factorial which is minus one factorial and minus one factorial is not defined.', 'start': 190.952, 'duration': 8.61}, {'end': 206.19, 'text': "so this definition works only for n, that is greater than or equal to one, but it doesn't work for zero.", 'start': 199.562, 'duration': 6.628}, {'end': 214.575, 'text': 'So actually, for this definition to be complete for factorials, we need to write n factorial as two separate cases.', 'start': 206.79, 'duration': 7.785}, {'end': 224.922, 'text': "So here we're going to write n factorial is equal to n times n minus 1 factorial if n is greater than or equal to 1.", 'start': 215.356, 'duration': 9.566}, {'end': 233.127, 'text': "And if that's not the case, or if n is equal to 0, I wrote otherwise here, n factorial is equal to 1.", 'start': 224.922, 'duration': 8.205}, {'end': 240.132, 'text': 'And this is actually a complete definition of all factorials for all positive integers and zero.', 'start': 233.127, 'duration': 7.005}, {'end': 248.499, 'text': "So let's just quickly see how we can use this new definition of factorials to find the factorial of any positive integer.", 'start': 240.653, 'duration': 7.846}, {'end': 249.74, 'text': "Let's say three.", 'start': 249.019, 'duration': 0.721}, {'end': 255.524, 'text': "So if you ask yourself, what's three factorial? There are two ways of answering that question.", 'start': 250.4, 'duration': 5.124}, {'end': 258.466, 'text': 'The first one would be to use the old definition.', 'start': 256.103, 'duration': 2.363}, {'end': 261.728, 'text': 'And then the second way would be to use this new definition.', 'start': 258.926, 'duration': 2.802}], 'summary': 'Factorial defined for n>=0, 0!=1, n! = n*(n-1)! for n>=1', 'duration': 74.159, 'max_score': 187.569, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU187569.jpg'}], 'start': 0.269, 'title': 'An introduction to recursion', 'summary': 'Introduces recursion through the explanation of factorials and their definition, with a demonstration of finding the factorial of a number, culminating in the value of 3 factorial being 6.', 'chapters': [{'end': 357.367, 'start': 0.269, 'title': 'Introduction to recursion', 'summary': 'Introduces recursion by explaining factorials and their definition, and demonstrates the process of finding the factorial of a number using a new definition, culminating in the value of 3 factorial being 6.', 'duration': 357.098, 'highlights': ['The process of finding the factorial of a number using the new definition is demonstrated, leading to the value of 3 factorial being 6.', 'The complete definition of factorials for all positive integers and zero is explained as n factorial = n * (n-1) factorial if n is greater than or equal to 1; otherwise n factorial is equal to 1.', 'The definition of factorials is broken down into separate cases, addressing the issue of zero factorial and providing a complete definition for all positive integers and zero.', 'The concept of recursion is introduced as a way of solving problems by having a function call itself in computer science.']}], 'duration': 357.098, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU269.jpg', 'highlights': ['The process of finding the factorial of a number using the new definition is demonstrated, leading to the value of 3 factorial being 6.', 'The complete definition of factorials for all positive integers and zero is explained as n factorial = n * (n-1) factorial if n is greater than or equal to 1; otherwise n factorial is equal to 1.', 'The concept of recursion is introduced as a way of solving problems by having a function call itself in computer science.', 'The definition of factorials is broken down into separate cases, addressing the issue of zero factorial and providing a complete definition for all positive integers and zero.']}, {'end': 714.812, 'segs': [{'end': 382.625, 'src': 'embed', 'start': 357.367, 'weight': 0, 'content': [{'end': 368.576, 'text': "fact of n and fact of n, as i said earlier, is going to take n, which is either a positive integer, or 0, and it's going to return n factorial.", 'start': 357.367, 'duration': 11.209}, {'end': 371.478, 'text': "So let's see how we can implement it using recursion.", 'start': 369.176, 'duration': 2.302}, {'end': 379.103, 'text': 'And actually, all you need to do for that is you need to translate this new definition of factorials into code.', 'start': 371.998, 'duration': 7.105}, {'end': 382.625, 'text': "So let's just bring this definition up here.", 'start': 379.583, 'duration': 3.042}], 'summary': 'Implementing n factorial using recursion for positive integers or 0.', 'duration': 25.258, 'max_score': 357.367, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU357367.jpg'}, {'end': 499.647, 'src': 'embed', 'start': 473.69, 'weight': 2, 'content': [{'end': 485.096, 'text': 'So, as you can see, this is a recursive function, because this calls itself fact, calls itself right here to solve the problem of finding n factorial.', 'start': 473.69, 'duration': 11.406}, {'end': 491, 'text': 'Okay, this function seems pretty simple, but does it actually work? Well, it does.', 'start': 485.817, 'duration': 5.183}, {'end': 494.162, 'text': "To see how, let's take a look at a few examples here.", 'start': 491.36, 'duration': 2.802}, {'end': 499.647, 'text': 'If you have fact of zero, I just wrote it as f of zero.', 'start': 495.063, 'duration': 4.584}], 'summary': "The recursive function 'fact' solves the problem of finding n factorial and works for f(0).", 'duration': 25.957, 'max_score': 473.69, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU473690.jpg'}], 'start': 357.367, 'title': 'Recursive factorial functions', 'summary': 'Discusses the implementation of a recursive factorial function in java, where the function takes a positive integer or 0 and returns its factorial. it explains a recursive function to find n factorial, exemplifying its working with examples of fact(0), fact(1), and fact(4), showcasing how the function correctly calculates the factorial values.', 'chapters': [{'end': 473.07, 'start': 357.367, 'title': 'Recursive factorial implementation in java', 'summary': 'Discusses the implementation of a recursive factorial function in java, where the function takes a positive integer or 0 and returns its factorial, with a specific focus on the translation of the factorial definition into code.', 'duration': 115.703, 'highlights': ['The function fact of n takes a positive integer or 0 and returns n factorial, with a specific focus on translating the factorial definition into Java code.', 'The translation of the formal factorial definition into code involves using recursion and defining the base case for n equals 0, where the function returns 1.']}, {'end': 714.812, 'start': 473.69, 'title': 'Recursive function for finding factorial', 'summary': 'Explains a recursive function to find n factorial, exemplifying its working with examples of fact(0), fact(1), and fact(4), showcasing how the function correctly calculates the factorial values.', 'duration': 241.122, 'highlights': ['The recursive function is demonstrated through examples of fact(0), fact(1), and fact(4), showcasing its accurate computation of factorial values.', "The explanation of the function's working includes a step-by-step breakdown of how the function correctly computes the factorial values for different inputs.", 'The function correctly evaluates the factorial for various inputs such as fact(0), fact(1), and fact(4), demonstrating its accuracy and reliability.']}], 'duration': 357.445, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU357367.jpg', 'highlights': ['The function fact of n takes a positive integer or 0 and returns n factorial, with a specific focus on translating the factorial definition into Java code.', 'The translation of the formal factorial definition into code involves using recursion and defining the base case for n equals 0, where the function returns 1.', "The explanation of the function's working includes a step-by-step breakdown of how the function correctly computes the factorial values for different inputs.", 'The recursive function is demonstrated through examples of fact(0), fact(1), and fact(4), showcasing its accurate computation of factorial values.', 'The function correctly evaluates the factorial for various inputs such as fact(0), fact(1), and fact(4), demonstrating its accuracy and reliability.']}, {'end': 1034.255, 'segs': [{'end': 782.344, 'src': 'heatmap', 'start': 719.437, 'weight': 1, 'content': [{'end': 722.059, 'text': 'Let me know in a comment below if anything was unclear.', 'start': 719.437, 'duration': 2.622}, {'end': 728.566, 'text': "Okay, now to better understand recursion, let's take a look at another example here, the Fibonacci sequence.", 'start': 722.7, 'duration': 5.866}, {'end': 732.448, 'text': 'so i already talked about this in one of my previous videos.', 'start': 729.247, 'duration': 3.201}, {'end': 738.35, 'text': 'but the fibonacci sequence is a sequence of numbers that starts with two ones at the beginning,', 'start': 732.448, 'duration': 5.902}, {'end': 743.452, 'text': 'and the numbers after that are generated by adding up the two previous numbers.', 'start': 738.35, 'duration': 5.102}, {'end': 752.456, 'text': 'so, for example, the third number is two because one plus one equals two, and then the fourth number is three, because one plus two equals three,', 'start': 743.452, 'duration': 9.004}, {'end': 755.057, 'text': 'and so on, and then it just keeps on going forever.', 'start': 752.456, 'duration': 2.601}, {'end': 757.679, 'text': 'And given this sequence,', 'start': 755.937, 'duration': 1.742}, {'end': 770.051, 'text': "let's just say that we're trying to solve the problem of writing a function let's say fib which takes a positive integer n and returns the nth number in this sequence,", 'start': 757.679, 'duration': 12.372}, {'end': 771.032, 'text': 'the nth Fibonacci number.', 'start': 770.051, 'duration': 0.981}, {'end': 782.344, 'text': "So if you're given 3 as n in this function, you should be able to find and return the third Fibonacci number, which is 2.", 'start': 771.813, 'duration': 10.531}], 'summary': 'Explaining recursion using fibonacci sequence with an example and problem-solving approach.', 'duration': 43.994, 'max_score': 719.437, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU719437.jpg'}, {'end': 825.024, 'src': 'embed', 'start': 799.715, 'weight': 0, 'content': [{'end': 806.736, 'text': 'Now to solve this problem using recursion, you need to first formally define the relation between different Fibonacci numbers,', 'start': 799.715, 'duration': 7.021}, {'end': 808.157, 'text': 'just like we did with factorials.', 'start': 806.736, 'duration': 1.421}, {'end': 812.917, 'text': "So for that, we're going to write Fn equals Fn-1 plus Fn-2.", 'start': 808.857, 'duration': 4.06}, {'end': 825.024, 'text': "So I'm denoting the nth Fibonacci number as Fn, and this is saying the nth Fibonacci number should be the sum of the two previous Fibonacci numbers.", 'start': 815.658, 'duration': 9.366}], 'summary': 'Using recursion to define the fibonacci sequence as fn = fn-1 + fn-2', 'duration': 25.309, 'max_score': 799.715, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU799715.jpg'}, {'end': 992.841, 'src': 'embed', 'start': 963.458, 'weight': 4, 'content': [{'end': 968.002, 'text': "Okay, let's now take a look at a few examples here to see how this function works exactly.", 'start': 963.458, 'duration': 4.544}, {'end': 970.365, 'text': "I'm just going to move this function over here.", 'start': 968.503, 'duration': 1.862}, {'end': 978.033, 'text': "okay, first of all, let's say this function fib is called with 3 as the argument.", 'start': 971.59, 'duration': 6.443}, {'end': 984.197, 'text': 'then what happens is we go to this line right here 3 is greater than or equal to 3.', 'start': 978.033, 'duration': 6.164}, {'end': 992.841, 'text': "so we'll say okay, the value, the return value of fib of 3 should be the sum of fib of 1 and fib of 2.", 'start': 984.197, 'duration': 8.644}], 'summary': 'Demonstrating how the fib function works with examples.', 'duration': 29.383, 'max_score': 963.458, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU963458.jpg'}], 'start': 715.833, 'title': 'Fibonacci sequence and its recursive solution', 'summary': 'Covers the explanation of the fibonacci sequence, a series of numbers formed by adding the two preceding numbers, along with an exploration of the recursive solution for finding the nth fibonacci number, including formal definition, code implementation, and an illustrative example.', 'chapters': [{'end': 757.679, 'start': 715.833, 'title': 'Understanding fibonacci sequence', 'summary': 'Explains the fibonacci sequence, which is a sequence of numbers generated by adding up the two previous numbers, starting with two ones, and it continues indefinitely.', 'duration': 41.846, 'highlights': ['The Fibonacci sequence starts with two ones at the beginning and the numbers after that are generated by adding up the two previous numbers.', 'The third number in the Fibonacci sequence is two because one plus one equals two, and the fourth number is three because one plus two equals three, and so on, continuing indefinitely.']}, {'end': 1034.255, 'start': 757.679, 'title': 'Solving fibonacci number problem using recursion', 'summary': "Discusses the problem of finding the nth fibonacci number using recursion, providing the formal definition and code implementation for the solution, with an example demonstrating the function's functionality.", 'duration': 276.576, 'highlights': ['The formal definition of the relation between different Fibonacci numbers is Fn = Fn-1 + Fn-2, with an exception for n=1 and n=2, where Fn=1.', 'The function fib(int n) is defined to return the nth Fibonacci number, using recursion to calculate the sum of the previous Fibonacci numbers when n is greater than or equal to 3.', 'The example demonstrates the functionality of the fib function, showing the recursive calculation of the third Fibonacci number as 2 by summing the first and second Fibonacci numbers.']}], 'duration': 318.422, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU715833.jpg', 'highlights': ['The formal definition of the relation between different Fibonacci numbers is Fn = Fn-1 + Fn-2, with an exception for n=1 and n=2, where Fn=1.', 'The Fibonacci sequence starts with two ones at the beginning and the numbers after that are generated by adding up the two previous numbers.', 'The function fib(int n) is defined to return the nth Fibonacci number, using recursion to calculate the sum of the previous Fibonacci numbers when n is greater than or equal to 3.', 'The third number in the Fibonacci sequence is two because one plus one equals two, and the fourth number is three because one plus two equals three, and so on, continuing indefinitely.', 'The example demonstrates the functionality of the fib function, showing the recursive calculation of the third Fibonacci number as 2 by summing the first and second Fibonacci numbers.']}, {'end': 1356.115, 'segs': [{'end': 1085.054, 'src': 'embed', 'start': 1034.255, 'weight': 0, 'content': [{'end': 1044.119, 'text': "in a function that uses recursion or in a recursive function, the condition where it doesn't call itself at all but instead returns, for example,", 'start': 1034.255, 'duration': 9.864}, {'end': 1051.263, 'text': 'just a number, is called a base case, and then the condition where it calls itself is called a recursive case.', 'start': 1044.119, 'duration': 7.144}, {'end': 1060.267, 'text': "So in this example, when n is greater than or equal to 3, that's a recursive case, and otherwise, that's a base case.", 'start': 1051.983, 'duration': 8.284}, {'end': 1063.068, 'text': "Let's take a look at another example here.", 'start': 1061.447, 'duration': 1.621}, {'end': 1067.769, 'text': "Let's say this function fib is called 4 as the argument.", 'start': 1063.708, 'duration': 4.061}, {'end': 1069.469, 'text': "That's this one right here.", 'start': 1068.349, 'duration': 1.12}, {'end': 1076.711, 'text': 'Then it goes to this line right here because n which is 4 is greater than or equal to 3.', 'start': 1070.17, 'duration': 6.541}, {'end': 1083.853, 'text': 'So we want to return fib of 3 plus fib of 2 as the return value of fib of 4.', 'start': 1076.711, 'duration': 7.142}, {'end': 1085.054, 'text': "So that's what I wrote here.", 'start': 1083.853, 'duration': 1.201}], 'summary': 'A recursive function has base and recursive cases. example: fib(4) calls fib(3) + fib(2).', 'duration': 50.799, 'max_score': 1034.255, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU1034255.jpg'}, {'end': 1235.156, 'src': 'embed', 'start': 1194.185, 'weight': 1, 'content': [{'end': 1201.186, 'text': "To see why it's not the most efficient way to do it and to see how you can fix it, you can just check my video about dynamic programming.", 'start': 1194.185, 'duration': 7.001}, {'end': 1205.947, 'text': 'Okay, and this was number six of my data structures and algorithm series.', 'start': 1201.726, 'duration': 4.221}, {'end': 1209.29, 'text': 'You can find the entire series in the description below.', 'start': 1206.607, 'duration': 2.683}, {'end': 1217.66, 'text': "And to close things off here, let me give you another practice problem for recursion, which comes from this video's sponsor, Boolean.org.", 'start': 1209.991, 'duration': 7.669}, {'end': 1228.631, 'text': "In this problem, there's a frog looking over a river, which is 11 feet wide, And there are 10 stones placed in this river, one foot apart.", 'start': 1218.14, 'duration': 10.491}, {'end': 1235.156, 'text': "So from the end of the river, the beginning of the river, I guess, to the first stone, that's one foot.", 'start': 1229.351, 'duration': 5.805}], 'summary': 'The video covers dynamic programming, data structures, and algorithms with a practice problem for recursion related to a frog crossing a river with 10 stones.', 'duration': 40.971, 'max_score': 1194.185, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU1194185.jpg'}, {'end': 1238.219, 'src': 'heatmap', 'start': 1194.185, 'weight': 0.893, 'content': [{'end': 1201.186, 'text': "To see why it's not the most efficient way to do it and to see how you can fix it, you can just check my video about dynamic programming.", 'start': 1194.185, 'duration': 7.001}, {'end': 1205.947, 'text': 'Okay, and this was number six of my data structures and algorithm series.', 'start': 1201.726, 'duration': 4.221}, {'end': 1209.29, 'text': 'You can find the entire series in the description below.', 'start': 1206.607, 'duration': 2.683}, {'end': 1217.66, 'text': "And to close things off here, let me give you another practice problem for recursion, which comes from this video's sponsor, Boolean.org.", 'start': 1209.991, 'duration': 7.669}, {'end': 1228.631, 'text': "In this problem, there's a frog looking over a river, which is 11 feet wide, And there are 10 stones placed in this river, one foot apart.", 'start': 1218.14, 'duration': 10.491}, {'end': 1235.156, 'text': "So from the end of the river, the beginning of the river, I guess, to the first stone, that's one foot.", 'start': 1229.351, 'duration': 5.805}, {'end': 1238.219, 'text': "And then to the next stone, that's one foot and so on.", 'start': 1235.636, 'duration': 2.583}], 'summary': 'Data structures and algorithm video series #6 covers dynamic programming and includes a practice problem for recursion sponsored by boolean.org.', 'duration': 44.034, 'max_score': 1194.185, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU1194185.jpg'}, {'end': 1309.869, 'src': 'embed', 'start': 1279.426, 'weight': 3, 'content': [{'end': 1286.928, 'text': "and a simpler version of this problem would be this one right here, where there's a frog on one side of the river, just like before,", 'start': 1279.426, 'duration': 7.502}, {'end': 1293.03, 'text': "but instead of 11 feet, this time the river is only two feet and there's only one stone placed.", 'start': 1286.928, 'duration': 6.102}, {'end': 1300.058, 'text': 'So in this example there are only two ways for this frog to go from this side to that side,', 'start': 1293.75, 'duration': 6.308}, {'end': 1309.869, 'text': 'because the first way would be to jump directly from this side to that side and then the second way would be to jump to the stone and then to that side of the river.', 'start': 1300.058, 'duration': 9.811}], 'summary': 'Frog has two ways to cross a 2-foot river with one stone.', 'duration': 30.443, 'max_score': 1279.426, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU1279426.jpg'}, {'end': 1347.662, 'src': 'embed', 'start': 1322.318, 'weight': 5, 'content': [{'end': 1329.082, 'text': 'Now, Brilliant is a website where you can practice your problem-solving abilities with interesting problems like these,', 'start': 1322.318, 'duration': 6.764}, {'end': 1330.463, 'text': "and that's really the best way to learn.", 'start': 1329.082, 'duration': 1.381}, {'end': 1334.366, 'text': 'So if you want more interesting problems about data structures,', 'start': 1331.024, 'duration': 3.342}, {'end': 1339.97, 'text': 'just go to brilliant.org slash csdojo and maybe check out their computer science fundamentals course.', 'start': 1334.366, 'duration': 5.604}, {'end': 1347.662, 'text': "There, you'll be able to find more interesting problems about topics like algorithms, recursion, stack and queues, and so on.", 'start': 1340.65, 'duration': 7.012}], 'summary': 'Brilliant.org offers practice for problem-solving in computer science with interesting problems and courses.', 'duration': 25.344, 'max_score': 1322.318, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU1322318.jpg'}], 'start': 1034.255, 'title': 'Recursion and frog jumping', 'summary': 'Covers recursion in the fibonacci function, showcasing an example yielding a value of 3, and explores a frog jumping problem with 10 stones and a wider river, along with a simpler version with 2 stones, offering 2 crossing ways.', 'chapters': [{'end': 1209.29, 'start': 1034.255, 'title': 'Recursion in fibonacci function', 'summary': 'Explains the concept of base case and recursive case in a recursive function, using an example of calculating the fourth fibonacci number using recursion, resulting in a value of 3. it also mentions that the demonstrated method is not the most efficient way and suggests referring to a video about dynamic programming for optimization.', 'duration': 175.035, 'highlights': ["The base case in a recursive function is when it doesn't call itself but instead returns a specific value, such as a number.", 'In the example of calculating the fourth Fibonacci number using recursion, the return value is explained step by step, resulting in the value of 3.', 'The demonstrated method for calculating the Fibonacci number is acknowledged as inefficient, and viewers are directed to a video about dynamic programming for optimization.', 'The entire series of data structures and algorithm videos, including this explanation, is available in the description below the video.']}, {'end': 1356.115, 'start': 1209.991, 'title': 'Frog jumping problem', 'summary': 'Discusses a frog jumping problem involving a river 11 feet wide with 10 stones, presenting a practice problem for recursion with the question of how many ways the frog can jump from one side to the other, and also mentions a simpler version with a 2-feet wide river and one stone, where only 2 ways exist for the frog to cross.', 'duration': 146.124, 'highlights': ['Recursion problem involving a frog and a river 11 feet wide with 10 stones, presenting the question of how many ways the frog can jump from one side to the other.', 'Simpler version with a 2-feet wide river and one stone, where only 2 ways exist for the frog to cross.', 'Promotion of Brilliant.org for practicing problem-solving abilities with interesting problems related to data structures and computer science fundamentals.']}], 'duration': 321.86, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/B0NtAFf4bvU/pics/B0NtAFf4bvU1034255.jpg', 'highlights': ["The base case in a recursive function is when it doesn't call itself but instead returns a specific value, such as a number.", 'Recursion problem involving a frog and a river 11 feet wide with 10 stones, presenting the question of how many ways the frog can jump from one side to the other.', 'In the example of calculating the fourth Fibonacci number using recursion, the return value is explained step by step, resulting in the value of 3.', 'Simpler version with a 2-feet wide river and one stone, where only 2 ways exist for the frog to cross.', 'The demonstrated method for calculating the Fibonacci number is acknowledged as inefficient, and viewers are directed to a video about dynamic programming for optimization.', 'Promotion of Brilliant.org for practicing problem-solving abilities with interesting problems related to data structures and computer science fundamentals.', 'The entire series of data structures and algorithm videos, including this explanation, is available in the description below the video.']}], 'highlights': ['The process of finding the factorial of a number using the new definition is demonstrated, leading to the value of 3 factorial being 6.', 'The complete definition of factorials for all positive integers and zero is explained as n factorial = n * (n-1) factorial if n is greater than or equal to 1; otherwise n factorial is equal to 1.', 'The concept of recursion is introduced as a way of solving problems by having a function call itself in computer science.', 'The definition of factorials is broken down into separate cases, addressing the issue of zero factorial and providing a complete definition for all positive integers and zero.', 'The function fact of n takes a positive integer or 0 and returns n factorial, with a specific focus on translating the factorial definition into Java code.', 'The translation of the formal factorial definition into code involves using recursion and defining the base case for n equals 0, where the function returns 1.', "The explanation of the function's working includes a step-by-step breakdown of how the function correctly computes the factorial values for different inputs.", 'The recursive function is demonstrated through examples of fact(0), fact(1), and fact(4), showcasing its accurate computation of factorial values.', 'The formal definition of the relation between different Fibonacci numbers is Fn = Fn-1 + Fn-2, with an exception for n=1 and n=2, where Fn=1.', 'The Fibonacci sequence starts with two ones at the beginning and the numbers after that are generated by adding up the two previous numbers.', 'The function fib(int n) is defined to return the nth Fibonacci number, using recursion to calculate the sum of the previous Fibonacci numbers when n is greater than or equal to 3.', 'The third number in the Fibonacci sequence is two because one plus one equals two, and the fourth number is three because one plus two equals three, and so on, continuing indefinitely.', 'The example demonstrates the functionality of the fib function, showing the recursive calculation of the third Fibonacci number as 2 by summing the first and second Fibonacci numbers.', "The base case in a recursive function is when it doesn't call itself but instead returns a specific value, such as a number.", 'Recursion problem involving a frog and a river 11 feet wide with 10 stones, presenting the question of how many ways the frog can jump from one side to the other.', 'In the example of calculating the fourth Fibonacci number using recursion, the return value is explained step by step, resulting in the value of 3.', 'Simpler version with a 2-feet wide river and one stone, where only 2 ways exist for the frog to cross.', 'The demonstrated method for calculating the Fibonacci number is acknowledged as inefficient, and viewers are directed to a video about dynamic programming for optimization.', 'Promotion of Brilliant.org for practicing problem-solving abilities with interesting problems related to data structures and computer science fundamentals.', 'The entire series of data structures and algorithm videos, including this explanation, is available in the description below the video.']}