Python Recursion Understanding Issue

Question

I'm a freshman in cs, and I am having a little issue understanding the content of recursion in python.

I have 3 questions that I want to ask, or to confirm if I am understanding the content correctly.

1: I'm not sure the purpose of using base case in recursion. Is base case worked to terminate the recursion somewhere in my program?

2: Suppose I have my recursive call above any other code of my program. Is the program going to run the recursion first and then to run the content after recursion?

3: How to trace recursion properly with a reasonable correctness rate? I personally think it's really hard to trace recursion and I can barely find some instruction online.

Thanks for answering my questions.

1. The base case is the terminal case for the recursion. 2. Yes, the recursive call has to terminate and fully unwind the stack before continuing. 3. Depth in the call stack is often useful for debugging, you can add an extra parameter which holds the depth for diagnostic printing. — AChampion
– AChampion, Commented Aug 14, 2017 at 1:52

Patrick Haugh · Accepted Answer · 2017-08-14 01:58:00Z

1

Yes. The idea is that the recursive call will continue to call itself (with different inputs) until it calls the base case (or one of many base cases). The base case is usually a case of your problem where the solution is trivial and doesn't rely on any other parts of the problem. It then walks through the calls backwards, building on the answer it got for the simplest version of the question.
Yes. Interacting with recursive functions from the outside is exactly the same as interacting with any other function.
Depends on what you're writing, and how comfortable you are with debugging tools. If you're trying to track what values are getting passed back and forth between recursive calls, printing all the parameters at the start of the function and the return value at the end can take you pretty far.

The easiest way to wrap your head around this stuff is to write some of your own. Start with some basic examples (the classic is the factorial function) and ask for help if you get stuck.

Edit: If you're more math-oriented, you might look up mathematical induction (you will learn it anyway as part of cs education). It's the exact same concept, just taught a little differently.

answered Aug 14, 2017 at 1:58

Patrick Haugh

61.3k13 gold badges94 silver badges101 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

John Hamlett IV Over a year ago

I know this question is for Python, however, if you know one language you know all of them. The way I learned recursion is this site, codingbat.com/java/Recursion-1. You could even just write the problems there in Python and learn some unit testing :)

Patrick Haugh Over a year ago

@JohnHamlettIV That's a good observation that I didn't mention in my answer. Recursion is language agnostic, and anyone trying to learn about it should be aware of that. (I'll take the python tag off of this question, you're right that it doesn't belong)

Collectives™ on Stack Overflow

Python Recursion Understanding Issue

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related