How does recursion terminate

Its the "door leads out of the maze". How do we know if a door leads out of the maze? We know because inside the next room going through the door , we ask the same question, how do we get out of the maze? What happens is the computer "remembers" all the "what ifs".

What if I take the first door, what if I take the second door, what if I take the next door, etc. And for every possible door you can move through, the computer remembers those what ifs, and for every door after that, and after that, etc, until the end is found. Answer: That was a trick question There is no base case in the code. You need to check at the start if the room is the exit.

If it is, no recursion! Answer: There are various techniques. If the room is a structure or object you can add the visited field direction to the room. Answer: The answer to that can be found by thinking about the following question: What would happen if the maze was a giant grid of identically sized rectangular rooms, each with doors on every wall?

Imagine you go North through the first door, then East through the next rooms door, then South through that rooms door, and then West through that rooms door. Where do you end up?

Back where you started! Worse, you might continue to make this loop for ever. How would a intrepid adventurer solve this problem? One answer to that is by using a piece of chalk and putting a big X on the floor of every room you enter. Thus when you come back to a room with an X on the floor, you know you needn't enter. In the case of the program, a boolean flag "seen" or "visited" should be used.

Every room has a flag. Every room starts with the flag being set to false. When you visit a room, you set the flag to true. Finally, in the "base case" you have a line such as:. Some Computer related examples include: Adding a list of numbers, Computing the Fibonacci sequence, computing a Factorial, and Sudoku. There are techniques that can be used to reduce the number of calls necessary.

One technique, called memoization , caches the results of expensive function calls so the result can be returned when the same input occurs again. This memoized version makes 35 function calls, which is much better than the of the original algorithm. It turns out that you can always solve a recursive problem iteratively -- however, for non-trivial problems, the recursive version is often much simpler to write and read.

Try it! Iterative functions those using a for-loop or while-loop are almost always more efficient than their recursive counterparts. This is because every time you call a function there is some amount of overhead that takes place in pushing and popping stack frames.

Iterative functions avoid this overhead. However, if the recursive algorithm is simpler to implement, it may make sense to start recursively and then optimize to an iterative algorithm later. Show Solution. Write a program that asks the user to enter a positive integer, and then uses a recursive function to print out the binary representation for that number. Use method 1 from lesson O.

This means your print statement should be after the recursive call. Hint: You can turn a negative integer into a positive one by converting it to an unsigned integer. These have identical bit representations the type is used to determine how to interpret the number into decimal. Best practice Generally favor iteration over recursion, except when recursion really makes sense. For example, a method which finds the latest i. The recursive calls keep breaking the smaller substrings in half until it reaches a base case, a single letter which just gets returned to the previous calls.

The later letters will bubble up through the recursive calls until finally the first invocation will return the later from the two halves of the original string. Stack Overflow for Teams — Collaborate and share knowledge with a private group. Create a free Team What is Teams? Collectives on Stack Overflow. Learn more. How does recursion know when to stop? Ask Question. Asked 7 years, 7 months ago. Active 7 years, 7 months ago.

Viewed 1k times. Improve this question. Recursion need a base case — jfly.