title
Re 4. Problems on Functional Recursion | Strivers A2Z DSA Course

description
Check our Website: https://www.takeuforward.org/ In case you are thinking to buy courses, please check below: Link to get 20% additional Discount at Coding Ninjas: https://bit.ly/3wE5aHx Code "takeuforward" for 15% off at GFG: https://practice.geeksforgeeks.org/courses Code "takeuforward" for 20% off on sys-design: https://get.interviewready.io?_aff=takeuforward Crypto, I use the Wazirx app: https://wazirx.com/invite/xexnpc4u Take 750 rs free Amazon Stock from me: https://indmoney.onelink.me/RmHC/idjex744 Earn 100 rs by making a Grow Account for investing: https://app.groww.in/v3cO/8hu879t0 Linkedin/Instagram/Telegram: https://linktr.ee/takeUforward ---------------------------------------------------------------------------------------------------------------------------------------------------- Please check out the entire channel for other sets of series on tougher and complex topics. Also do consider subscribing :) Please check out the SDE sheet which the entire country is using and getting placed at top-notch companies: https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/ Checkout Striver's Handles: https://linktr.ee/takeUforward

detail
{'title': 'Re 4. Problems on Functional Recursion | Strivers A2Z DSA Course', 'heatmap': [{'end': 351.116, 'start': 330.873, 'weight': 0.724}, {'end': 619.702, 'start': 605.879, 'weight': 1}], 'summary': 'The course covers recursion in array reversal and palindrome check, emphasizing implementation logic and providing examples, like using a single pointer and formula, n - i - 1, for array swapping, and explaining recursive palindrome check with time complexity of n by 2 and space complexity of n by 2.', 'chapters': [{'end': 325.228, 'segs': [{'end': 48.946, 'src': 'embed', 'start': 0.189, 'weight': 0, 'content': [{'end': 1.47, 'text': 'hey, everyone, welcome back to the channel.', 'start': 0.189, 'duration': 1.281}, {'end': 2.911, 'text': 'i hope you guys are doing extremely well.', 'start': 1.47, 'duration': 1.441}, {'end': 8.735, 'text': 'so today we will be, uh again doing one more, i think, couple of more problems on recursion,', 'start': 2.911, 'duration': 5.824}, {'end': 16.481, 'text': 'the first one being we will be learning how to reverse an array using recursion, definitely,', 'start': 8.735, 'duration': 7.746}, {'end': 23.967, 'text': 'and after that we will be learning how to check if a given string is palindrome or not using recursion.', 'start': 16.481, 'duration': 7.486}, {'end': 25.148, 'text': 'now, reverse an array.', 'start': 23.967, 'duration': 1.181}, {'end': 26.728, 'text': "Let's understand.", 'start': 26.127, 'duration': 0.601}, {'end': 31.291, 'text': "If I am giving you something like, let's say this.", 'start': 27.428, 'duration': 3.863}, {'end': 33.413, 'text': 'This is the array that I am giving you.', 'start': 31.712, 'duration': 1.701}, {'end': 37.076, 'text': 'And I ask you to reverse this.', 'start': 34.154, 'duration': 2.922}, {'end': 41.998, 'text': 'So, the reverse will be definitely something like 2, 4, 3, 2, 1.', 'start': 37.636, 'duration': 4.362}, {'end': 44.502, 'text': 'I think there is no doubt that the reverse will be this.', 'start': 42, 'duration': 2.502}, {'end': 47.284, 'text': "If you don't understand what is reverse, I can't help.", 'start': 45.343, 'duration': 1.941}, {'end': 48.946, 'text': 'So, this is what the reverse will be.', 'start': 47.765, 'duration': 1.181}], 'summary': 'Learning recursion by solving problems: array reversal and palindrome check.', 'duration': 48.757, 'max_score': 0.189, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/twuC1F6gLI8/pics/twuC1F6gLI8189.jpg'}, {'end': 157.542, 'src': 'embed', 'start': 127.191, 'weight': 1, 'content': [{'end': 128.051, 'text': "And let's keep a pointer at R.", 'start': 127.191, 'duration': 0.86}, {'end': 132.446, 'text': "So, I swap L and R and that's my recursion's task.", 'start': 128.743, 'duration': 3.703}, {'end': 138.57, 'text': 'My recursion task will be to swap and then again call the recursion to swap the next index.', 'start': 132.926, 'duration': 5.644}, {'end': 140.771, 'text': 'Apparently, the next index should have been this.', 'start': 139.27, 'duration': 1.501}, {'end': 148.756, 'text': "So if you logically think it's swap and call the next L and the before R right?", 'start': 141.391, 'duration': 7.365}, {'end': 151.658, 'text': "So if you're going to think in that direction, I think you can write recursion.", 'start': 149.157, 'duration': 2.501}, {'end': 154.44, 'text': 'Until how long? L, R, L, R, L, R.', 'start': 152.039, 'duration': 2.401}, {'end': 157.542, 'text': "The moment they cross or they overlap, you're going to stop.", 'start': 154.44, 'duration': 3.102}], 'summary': 'Recursively swap l and r until they cross or overlap.', 'duration': 30.351, 'max_score': 127.191, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/twuC1F6gLI8/pics/twuC1F6gLI8127191.jpg'}], 'start': 0.189, 'title': 'Recursion in array reversal & palindrome check', 'summary': 'Focuses on using recursion to reverse arrays and check palindromes, with emphasis on implementation logic. it explains array reversal with recursion using variables, achieving successful reversal.', 'chapters': [{'end': 210.613, 'start': 0.189, 'title': 'Recursion: reversing arrays & checking palindromes', 'summary': 'Focuses on learning how to reverse an array using recursion and implement recursion to check if a given string is a palindrome, emphasizing the process and logic behind the implementations.', 'duration': 210.424, 'highlights': ['The process of reversing an array using recursion is explained, with a logical step-by-step approach and the identification of the limiting case for the recursion.', 'The concept of using two pointers for recursion is introduced, with a clear explanation of the swapping process and the condition for stopping the recursion.', 'The logic and approach for implementing recursion to check for palindromes in a string is discussed, including the identification of the base case and the recursive tasks involved.']}, {'end': 325.228, 'start': 211.613, 'title': 'Recursion in reversing an array', 'summary': 'Explains the process of reversing an array using recursion, using a simple example and the use of variables l and r, resulting in the successful reversal of the array.', 'duration': 113.615, 'highlights': ["The process of reversing an array using recursion is demonstrated by using the example of a simple array '1, 3, 2, 3' being successfully reversed.", 'The explanation involves the use of variables l and r to keep track of the indices, and the process ultimately results in the successful reversal of the entire array.']}], 'duration': 325.039, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/twuC1F6gLI8/pics/twuC1F6gLI8189.jpg', 'highlights': ['The process of reversing an array using recursion is explained, with a logical step-by-step approach and the identification of the limiting case for the recursion.', 'The concept of using two pointers for recursion is introduced, with a clear explanation of the swapping process and the condition for stopping the recursion.', 'The logic and approach for implementing recursion to check for palindromes in a string is discussed, including the identification of the base case and the recursive tasks involved.', "The process of reversing an array using recursion is demonstrated by using the example of a simple array '1, 3, 2, 3' being successfully reversed.", 'The explanation involves the use of variables l and r to keep track of the indices, and the process ultimately results in the successful reversal of the entire array.']}, {'end': 605.319, 'segs': [{'end': 358.82, 'src': 'heatmap', 'start': 330.873, 'weight': 0, 'content': [{'end': 335.216, 'text': 'can you, uh, do this using a very single pointer?', 'start': 330.873, 'duration': 4.343}, {'end': 336.137, 'text': 'yes, we can.', 'start': 335.216, 'duration': 0.921}, {'end': 337.799, 'text': "let's understand how.", 'start': 336.137, 'duration': 1.662}, {'end': 351.116, 'text': 'so if i again write the same array, if i say this is the ith pointer, which is 0, 1, 2, 3, 4, and i say n is equal to 5.', 'start': 337.799, 'duration': 13.317}, {'end': 355.358, 'text': 'for this i, this guy is the.', 'start': 351.116, 'duration': 4.242}, {'end': 358.82, 'text': "this index is what you'll swap it for this i.", 'start': 355.358, 'duration': 3.462}], 'summary': 'Using a single pointer to swap array elements, with n=5.', 'duration': 33.592, 'max_score': 330.873, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/twuC1F6gLI8/pics/twuC1F6gLI8330873.jpg'}, {'end': 448.836, 'src': 'embed', 'start': 412.589, 'weight': 1, 'content': [{'end': 415.932, 'text': 'if you carefully observe, this is two.', 'start': 412.589, 'duration': 3.343}, {'end': 418.515, 'text': 'n was 5.', 'start': 417.114, 'duration': 1.401}, {'end': 429.642, 'text': "so i can say at any moment i crosses n by 2, because whenever you're crossing the middle there's no need to swap before that.", 'start': 418.515, 'duration': 11.127}, {'end': 432.404, 'text': 'you can just keep on swapping the left and the right guys.', 'start': 429.642, 'duration': 2.762}, {'end': 448.836, 'text': 'so i can again write these in this way that okay, f of, uh, f of something as i and i can say if i crosses n by 2, Then I can definitely return.', 'start': 432.404, 'duration': 16.432}], 'summary': 'Algorithm analysis: n=5, crossing middle, swapping left and right', 'duration': 36.247, 'max_score': 412.589, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/twuC1F6gLI8/pics/twuC1F6gLI8412589.jpg'}, {'end': 605.319, 'src': 'embed', 'start': 556.519, 'weight': 2, 'content': [{'end': 562.761, 'text': "you can take it and you can say int n and it'll be like okay, at any moment i crosses n by two.", 'start': 556.519, 'duration': 6.242}, {'end': 563.841, 'text': 'there is no need to do anything.', 'start': 562.761, 'duration': 1.08}, {'end': 574.062, 'text': 'you can return or else you can simply swap array of i, comma, array of n, minus i, minus one.', 'start': 563.841, 'duration': 10.221}, {'end': 578.146, 'text': "once you've done this, you can say f of i plus one comma array comma n.", 'start': 574.062, 'duration': 4.084}, {'end': 580.548, 'text': 'so these are the extra parameters that you will carry.', 'start': 578.146, 'duration': 2.402}, {'end': 583.63, 'text': 'nothing special, just the extra parameters that you will carry.', 'start': 580.548, 'duration': 3.082}, {'end': 592.676, 'text': 'and once you have done this, you can definitely, uh, print the array, which is something like for int i equal to zero, i less than n, i plus plus,', 'start': 583.63, 'duration': 9.046}, {'end': 594.437, 'text': 'and you can do nc out of array of i.', 'start': 592.676, 'duration': 1.761}, {'end': 596.737, 'text': 'Remember, arrays are passed using reference.', 'start': 594.437, 'duration': 2.3}, {'end': 597.957, 'text': "So, that's okay.", 'start': 597.237, 'duration': 0.72}, {'end': 605.319, 'text': "So, if I give 1, 2, 3, 4, 5, and if I just run this, you'll see this running.", 'start': 599.398, 'duration': 5.921}], 'summary': 'Explanation of a function with extra parameters and array printing.', 'duration': 48.8, 'max_score': 556.519, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/twuC1F6gLI8/pics/twuC1F6gLI8556519.jpg'}], 'start': 325.228, 'title': 'Array operations', 'summary': 'Explores single variable array swapping using a single pointer and a formula, n - i - 1, for swapping array elements, and discusses an array reversal algorithm using a recursive approach in c++, with a sample input of [1, 2, 3, 4, 5].', 'chapters': [{'end': 525.592, 'start': 325.228, 'title': 'Single variable array swapping', 'summary': 'Explains how to swap array elements using a single pointer, demonstrating that it can be done by using the formula n - i - 1, where n is the length of the array and i is the current index, and it also highlights the condition for stopping the swapping process when i crosses n by 2.', 'duration': 200.364, 'highlights': ['The swapping of array elements can be achieved using a single pointer through the formula n - i - 1, where n is the length of the array and i is the current index, simplifying the process and reducing the need for multiple pointers.', 'The condition for stopping the swapping process is when the current index, i, crosses n by 2, as at that point there is no need to swap before the middle of the array, simplifying the swapping algorithm.']}, {'end': 605.319, 'start': 525.592, 'title': 'Array reversal algorithm', 'summary': 'Discusses a recursive algorithm for array reversal, passing an array as a reference, and printing the reversed array, using c++ as an example, with a sample input of [1, 2, 3, 4, 5].', 'duration': 79.727, 'highlights': ["The recursive function 'f' is used to reverse the array, swapping elements at positions i and n - i - 1 until i crosses n by two, with an implementation in C++.", "The array is passed using reference, allowing modifications within the function 'f'.", 'The reversed array is printed using a for loop, demonstrating the successful reversal of the input array [1, 2, 3, 4, 5].']}], 'duration': 280.091, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/twuC1F6gLI8/pics/twuC1F6gLI8325228.jpg', 'highlights': ['The swapping of array elements can be achieved using a single pointer through the formula n - i - 1, simplifying the process and reducing the need for multiple pointers.', 'The condition for stopping the swapping process is when the current index, i, crosses n by 2, simplifying the swapping algorithm.', "The recursive function 'f' is used to reverse the array, swapping elements at positions i and n - i - 1 until i crosses n by two, with an implementation in C++.", "The array is passed using reference, allowing modifications within the function 'f'.", 'The reversed array is printed using a for loop, demonstrating the successful reversal of the input array [1, 2, 3, 4, 5].']}, {'end': 879.998, 'segs': [{'end': 636.528, 'src': 'heatmap', 'start': 605.879, 'weight': 2, 'content': [{'end': 606.999, 'text': "It's automatically swapped.", 'start': 605.879, 'duration': 1.12}, {'end': 611.4, 'text': 'Did you see this? So, this is how the swap function works.', 'start': 607.139, 'duration': 4.261}, {'end': 612.84, 'text': 'So, I hope you have understood.', 'start': 611.92, 'duration': 0.92}, {'end': 614.081, 'text': 'Again, a void function.', 'start': 612.941, 'duration': 1.14}, {'end': 619.702, 'text': 'A void function, which a recursion which does a task and calls the next index function.', 'start': 614.581, 'duration': 5.121}, {'end': 622.043, 'text': 'to do the next task.', 'start': 620.362, 'duration': 1.681}, {'end': 627.705, 'text': "So in recursion, it's very specific to identify which task does the recursion need to do.", 'start': 622.323, 'duration': 5.382}, {'end': 631.806, 'text': 'Like over here, the recursion has to do a task of swapping.', 'start': 627.965, 'duration': 3.841}, {'end': 633.347, 'text': 'You need to understand that.', 'start': 631.866, 'duration': 1.481}, {'end': 636.528, 'text': "If you've understood this, recursion is very straightforward.", 'start': 633.707, 'duration': 2.821}], 'summary': "Recursion involves swapping in a void function. it's straightforward if understood.", 'duration': 30.649, 'max_score': 605.879, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/twuC1F6gLI8/pics/twuC1F6gLI8605879.jpg'}, {'end': 682.379, 'src': 'embed', 'start': 654.361, 'weight': 0, 'content': [{'end': 659.444, 'text': 'We will be giving the string to a function and the function is going to tell us true or false.', 'start': 654.361, 'duration': 5.083}, {'end': 663.527, 'text': "If the string is palindrome, the function is going to say true, it's a palindrome.", 'start': 660.005, 'duration': 3.522}, {'end': 666.929, 'text': 'If the string is not a palindrome, the function is going to say false.', 'start': 663.927, 'duration': 3.002}, {'end': 669.591, 'text': 'This is not a palindrome.', 'start': 667.41, 'duration': 2.181}, {'end': 671.973, 'text': 'So, you have to write a functional kind of thing.', 'start': 669.711, 'duration': 2.262}, {'end': 674.595, 'text': "So, for an example, let's understand what is a palindrome.", 'start': 672.393, 'duration': 2.202}, {'end': 677.456, 'text': 'So, the definition of a palindrome is a string.', 'start': 675.095, 'duration': 2.361}, {'end': 682.379, 'text': 'on reversal reads the same.', 'start': 678.557, 'duration': 3.822}], 'summary': 'Function checks if string is a palindrome: true/false output.', 'duration': 28.018, 'max_score': 654.361, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/twuC1F6gLI8/pics/twuC1F6gLI8654361.jpg'}], 'start': 605.879, 'title': 'Recursion and palindrome check', 'summary': 'Covers the explanation of recursion and how to check if a given string is a palindrome, with an emphasis on understanding the concepts and writing functional code.', 'chapters': [{'end': 879.998, 'start': 605.879, 'title': 'Recursion and palindrome check', 'summary': 'Covers the explanation of recursion and how to check if a given string is a palindrome, with an emphasis on understanding the concepts and writing functional code.', 'duration': 274.119, 'highlights': ['Explaining recursion and its specific task of swapping The explanation of recursion emphasizes its specific task of swapping and the need to understand which task the recursion needs to perform.', 'Defining and checking for palindromes with functional code The chapter discusses the definition of a palindrome and emphasizes the need to write functional code to check if a given string is a palindrome, focusing on the concept of reversing and checking for equality.', 'Utilizing a functional approach to check for palindrome equality The discussion covers the functional approach of checking if two characters are equal and then recursively checking the upcoming indexes to determine if a given string is a palindrome.']}], 'duration': 274.119, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/twuC1F6gLI8/pics/twuC1F6gLI8605879.jpg', 'highlights': ['Defining and checking for palindromes with functional code The chapter discusses the definition of a palindrome and emphasizes the need to write functional code to check if a given string is a palindrome, focusing on the concept of reversing and checking for equality.', 'Utilizing a functional approach to check for palindrome equality The discussion covers the functional approach of checking if two characters are equal and then recursively checking the upcoming indexes to determine if a given string is a palindrome.', 'Explaining recursion and its specific task of swapping The explanation of recursion emphasizes its specific task of swapping and the need to understand which task the recursion needs to perform.']}, {'end': 1178.472, 'segs': [{'end': 1008.297, 'src': 'embed', 'start': 975.879, 'weight': 3, 'content': [{'end': 978.08, 'text': 'So, this guy says palindrome.', 'start': 975.879, 'duration': 2.201}, {'end': 980.281, 'text': 'Yes, this guy says palindrome.', 'start': 978.26, 'duration': 2.021}, {'end': 985.502, 'text': 'Right? So, madam works fine.', 'start': 980.681, 'duration': 4.821}, {'end': 987.723, 'text': "Let's try to take another example.", 'start': 985.882, 'duration': 1.841}, {'end': 991.965, 'text': 'Something like madmadsum.', 'start': 988.003, 'duration': 3.962}, {'end': 995.106, 'text': 'So, this is not a palindrome.', 'start': 993.585, 'duration': 1.521}, {'end': 998.907, 'text': 'Why? Because this guy and this guy are not equal.', 'start': 995.186, 'duration': 3.721}, {'end': 1000.728, 'text': 'Because on reversing, they will not be equal.', 'start': 999.367, 'duration': 1.361}, {'end': 1001.808, 'text': "So, let's see how this works.", 'start': 1000.988, 'duration': 0.82}, {'end': 1005.395, 'text': 'So, at the first time, F of 0 comes again.', 'start': 1002.833, 'duration': 2.562}, {'end': 1008.297, 'text': 'S of 0, S of 4.', 'start': 1006.536, 'duration': 1.761}], 'summary': 'Discussion on palindromes and examples of non-palindromic strings.', 'duration': 32.418, 'max_score': 975.879, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/twuC1F6gLI8/pics/twuC1F6gLI8975879.jpg'}, {'end': 1168.582, 'src': 'embed', 'start': 1142.178, 'weight': 0, 'content': [{'end': 1146.518, 'text': "the time complexity is n by two because you're going till only the half.", 'start': 1142.178, 'duration': 4.34}, {'end': 1152.292, 'text': "you're going only till the half right, and the space complexity will also be auxiliary stack space.", 'start': 1146.518, 'duration': 5.774}, {'end': 1155.29, 'text': 'nothing like significant, like No containers are used.', 'start': 1152.292, 'duration': 2.998}, {'end': 1160.855, 'text': "Internal stack space is n by 2 because half of the recursion calls will be waiting if it's a palindrome.", 'start': 1155.67, 'duration': 5.185}, {'end': 1164.439, 'text': "Correct? So that's how the time complexity and space complexity will be.", 'start': 1161.195, 'duration': 3.244}, {'end': 1168.582, 'text': "And I hope you've understood the entire concept, everything.", 'start': 1165.359, 'duration': 3.223}], 'summary': 'Time complexity: o(n/2), space complexity: auxiliary stack space, no containers used. internal stack space: o(n/2) due to palindrome check.', 'duration': 26.404, 'max_score': 1142.178, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/twuC1F6gLI8/pics/twuC1F6gLI81142178.jpg'}], 'start': 879.998, 'title': 'Recursive palindrome check', 'summary': "Explains how to write a functional recursive function to check for palindromic strings, including examples with 'madam' and 'madmadsum', highlighting the time complexity of n by 2 and the space complexity of n by 2 for the recursive calls.", 'chapters': [{'end': 1178.472, 'start': 879.998, 'title': 'Recursive palindrome check', 'summary': "Explains how to write a functional recursive function to check for palindromic strings, including examples with 'madam' and 'madmadsum', highlighting the time complexity of n by 2 and the space complexity of n by 2 for the recursive calls.", 'duration': 298.474, 'highlights': ["The chapter explains how to write a functional recursive function to check for palindromic strings, including examples with 'madam' and 'madmadsum', highlighting the time complexity of n by 2 and the space complexity of n by 2 for the recursive calls.", 'The function iterates till half the length of the string, leading to a time complexity of n by 2 for the recursive calls.', 'The space complexity is n by 2 due to the auxiliary stack space used for the recursive calls.', "Examples with 'madam' and 'madmadsum' demonstrate the functional recursive function's ability to check for palindromic strings."]}], 'duration': 298.474, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/twuC1F6gLI8/pics/twuC1F6gLI8879998.jpg', 'highlights': ["The chapter explains how to write a functional recursive function to check for palindromic strings, including examples with 'madam' and 'madmadsum', highlighting the time complexity of n by 2 and the space complexity of n by 2 for the recursive calls.", 'The function iterates till half the length of the string, leading to a time complexity of n by 2 for the recursive calls.', 'The space complexity is n by 2 due to the auxiliary stack space used for the recursive calls.', "Examples with 'madam' and 'madmadsum' demonstrate the functional recursive function's ability to check for palindromic strings."]}], 'highlights': ['The process of reversing an array using recursion is explained, with a logical step-by-step approach and the identification of the limiting case for the recursion.', 'The concept of using two pointers for recursion is introduced, with a clear explanation of the swapping process and the condition for stopping the recursion.', 'The logic and approach for implementing recursion to check for palindromes in a string is discussed, including the identification of the base case and the recursive tasks involved.', 'The swapping of array elements can be achieved using a single pointer through the formula n - i - 1, simplifying the process and reducing the need for multiple pointers.', 'The condition for stopping the swapping process is when the current index, i, crosses n by 2, simplifying the swapping algorithm.', 'Defining and checking for palindromes with functional code The chapter discusses the definition of a palindrome and emphasizes the need to write functional code to check if a given string is a palindrome, focusing on the concept of reversing and checking for equality.', "The chapter explains how to write a functional recursive function to check for palindromic strings, including examples with 'madam' and 'madmadsum', highlighting the time complexity of n by 2 and the space complexity of n by 2 for the recursive calls.", 'The function iterates till half the length of the string, leading to a time complexity of n by 2 for the recursive calls.', 'The space complexity is n by 2 due to the auxiliary stack space used for the recursive calls.']}