FAQ: Recursion: Conceptual - Base Case and Recursive Step

This community-built FAQ covers the “Base Case and Recursive Step” exercise from the lesson “Recursion: Conceptual”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Learn Recursion: Python

FAQs on the exercise Base Case and Recursive Step

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

This lesson mentions that stack overflow can occur when there is no base case in a recursive function or when the recursive step does not lead to the base case. I can imagine how stack overflow would occur in the latter case but not in the first one. Could anyone please provide me an example of how stack overflow would occur if there was no base case? The reason I ask is because even if there is no base case, wouldn’t the recursive step bring us closer to the base case and then raise an exception because the input can longer be made “smaller”(instead of a stack overflow exception?). For example, we could have a recursive function that deals with lists and has a recursive step which makes the list smaller and smaller but it has no base case. In this case, instead of raising a stack overflow exception, wouldn’t we get an out of index error. I’d appreciate any help clearing this up for me!

1 Like

Actually, in Python, you get RecursionError: maximum recursion depth exceeded

The “maximum recursion depth” is probably implementation dependent, but it seems to be 1000 in my Python 3.6 installation:

Type "copyright", "credits" or "license()" for more information.
>>> def fib_recur(n):
    # base case
#    if n == 0:
#        return 1
#    if n == 1:
#        return 1
    return fib_recur(n-1) + fib_recur(n-2)

>>> print(fib_recur(3))
Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    print(fib_recur(3))
  File "<pyshell#1>", line 7, in fib_recur
    return fib_recur(n-1) + fib_recur(n-2)
  File "<pyshell#1>", line 7, in fib_recur
    return fib_recur(n-1) + fib_recur(n-2)
  File "<pyshell#1>", line 7, in fib_recur
    return fib_recur(n-1) + fib_recur(n-2)
  [Previous line repeated 990 more times]
RecursionError: maximum recursion depth exceeded
>>> 

… and, yes, whichever error you reach first wins!

4 Likes

It’s probably me, but whilst I think I understand recursion (kind-a) these two paragraphs have me stumped:

1: What is a Big O runtime
2: O(N) is new to me? Did I miss a page out? I’m guessing it’s ‘big O’ again? Roy Orbison was a great guy but…
3: I can guess, but don’t think I have been told what a ‘linear runtime’ is either?

¿que?

" Analyzing the Big O runtime of a recursive function is very similar to analyzing an iterative function. Substitute iterations of a loop with recursive calls.

For example, if we loop through once for each element printing the value, we have a O(N) or linear runtime. Similarly, if we have a single recursive call for each element in the original function call, we have a O(N) or linear runtime."

2 Likes

There’s a course called “asymptotic notation” – it’s in the pro Computer Science course which covers this immediately before recursion. I think the recursion course assumes you’ve covered asymptotic notation. If you’ve not got a pro account, you might be able to view the cheatsheet here - https://www.codecademy.com/learn/paths/computer-science/tracks/cspath-asymptotic-notation/modules/cspath-asymptotic-notation/cheatsheet

2 Likes

actually this is annoying after recursion as the curriculum stands now… but this is actually answering another question I had posted elsewhere… good to know its called asymptotic notation I only encounter it in the wilds of Youtube as big O time with okayish explainers… Excited to finally get better insight into this.

Asymptotic notation is actually a broader term and big-O notation is a type of asymptotic notation. Big-O specifically describes the asymptotic upper bound of a function (in other words, the worst-case scenario). This resource might be helpful in understanding asymptotic notation.

I completed the Learn Recursion with Python course before the Computer Science Career Path, and I admit, some of the sections about big-O notation were a bit confusing. You can take a look at the cheatsheet for this unit which has a brief explanation of big-O and how it relates to recursion (definitely helpful when I took the course).

Both the Pass the Technical Interview with Python Skill Path and Computer Science Career Path have units on asymptotic notation. I’ve linked the cheatsheets for those units here. The units are nearly identical but the Pass the Technical Interview with Python Skill Path has an extra article on space complexity (the Learn Recursion with Python course deals with time complexity but space complexity is an important concept to understand as well).

Happy coding!

1 Like

Totally … I’m super excited to grab better insight into space complexity usage as well. I feel like the answers to most of the dynamic programming challenges are almost always O n 2 hahah … Did you enjoy the Python course. I finished another one but not on this platform. I’m going to tackle that as soon as I finish the technical javascript one. I’ve noticed a couple of sample problems my friends who are gainfully employed always ask it in the sample interview questions so its something I want to figure out hard.

Happy Coding and New Year to you too as well :wink:

1 Like

Which Python course are you referring to? I’ve completed several Python-related courses and paths here on CC and I enjoyed them. :slight_smile:

Thanks for getting back to me what I meant was it was on another code learning platform!! But obvs eager to tackle Python on here !!!

1 Like

I haven’t taken Python “courses” on a platform other than CC, but I’ve definitely learnt a lot from websites and other resources. Maybe try asking on the forums/community of that other platform you are referring to.

Can help me with this question:
Can we rewrite any iterative function in a recursive way? Why or why not?
Explain for me.

2 Likes