[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Non-recursive backtracking, using a stack

Posted on 2016-10-26
1
Medium Priority
?
738 Views
Last Modified: 2016-11-08
Hi,

I was going through below link

http://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html

what is difference between
Non-recursive backtracking, using a stack and
Non-recursive backtracking without using a stack

what is difference between
Non-recursive backtracking and recursive backtracking
please advise
0
Comment
Question by:gudii9
1 Comment
 
LVL 9

Accepted Solution

by:
James Bilous earned 2000 total points
ID: 41860708
When you make recursive calls you are using a naturally occuring memory "call stack". This call stack is simply how your machine keeps track of functions that were previously called so that when you return, you can be placed back into the function where you left off. When you are using recursion to search a tree, you can exploit this naturally occuring stack to backtrack. Each recursive call to your function essentially keeps track of a single visit to a node in your tree.

When you don't use recursion, you have to use your own data structure called a Stack to emulate this behavior. The stack data structure will keep tabs of each node you visit rather than your function calls doing this for you in a recursive implementation.
0

Featured Post

Important Lessons on Recovering from Petya

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What do responsible coders do? They don't take detrimental shortcuts. They do take reasonable security precautions, create important automation, implement sufficient logging, fix things they break, and care about users.
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
With the power of JIRA, there's an unlimited number of ways you can customize it, use it and benefit from it. With that in mind, there's bound to be things that I wasn't able to cover in this course. With this summary we'll look at some places to go…
Starting up a Project
Suggested Courses
Course of the Month19 days, 7 hours left to enroll

834 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question