Solved

Non-recursive backtracking, using a stack

Posted on 2016-10-26
1
133 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 8

Accepted Solution

by:
James Bilous earned 500 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

3 Use Cases for Connected Systems

Our Dev teams are like yours. They’re continually cranking out code for new features/bugs fixes, testing, deploying, testing some more, responding to production monitoring events and more. It’s complex. So, we thought you’d like to see what’s working for us.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
diffSum example 4 37
SHA2 certs for IIS AND Java? 2 88
hibernate example for saving data 19 39
VB.net and sql server 4 35
When we want to run, execute or repeat a statement multiple times, a loop is necessary. This article covers the two types of loops in Python: the while loop and the for loop.
Computer science students often experience many of the same frustrations when going through their engineering courses. This article presents seven tips I found useful when completing a bachelors and masters degree in computing which I believe may he…
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

773 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