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."

1 Like

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

1 Like