List and recursion

Question

RehabReda 0 Light Poster

17 Years Ago

hi guys:) i am facing a problem:-/
it is a recursive function and one of its parameters is of type list
when the function reaches its end and goes back the list won't be like the old one:?: but it will be updated with the newer on in the last function
see this code it is a code for a program to make a permutation of 5 numbers 0 1 2 3 4

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace _recursion
{
    class Program
    {
        public void recursion(List<int>history,List<int > available)
        {
            if (available.Count == 0)
            {
                for (int i = 0; i < history.Count; i++)
                {
                    Console.Write(history[i].ToString() + "->");
                }
                Console.WriteLine(" ");
                return;
            }
            for (int i = 0; i < available.Count; i++)
            {
                history.Add(available[i]);
                available.RemoveAt(i);
                recursion(history,available );

                available.Add(history[history.Count - 1]);
                 history.RemoveAt(history.Count - 1);



            }
            return;
        }
        bool[] b = new bool[5]; int [] place = new int [5];
          
        public List<int> find_available_places(List <int > available)
        {
            for (int i = 0; i < 5; i++)
            {
                place[i] = i;
            }
        
          
            for (int i = 0; i < 5; i++)
            {
                if (b[i] == false)
                {
                    available.Add(place[i]);
                }
            }
            return available;

        }
        static void Main(string[] args)
        {
           
            Program p = new Program();
            p.recursion(new List<int>(),p.find_available_places(new List<int>()));

        }
    }
}

.net:c# recursion

3 Contributors
9 Replies
2K Views
1 Day Discussion Span
Latest Post 17 Years Ago Latest Post by DdoubleD

Dani AI

Generated 11 Months Ago

Good catch, . The core issue is that List<T> is a reference type in C#. Each recursive call sees the same list instance unless you explicitly undo your changes or pass copies. When you RemoveAt(i) while iterating, indices shift, and when you later Add(...) you are not restoring the element to the same position. That is why the list does not look like it did at the start of the frame. If you want to reuse the same lists, you must backtrack precisely: take, explore, then un-take by putting the value back at the same index with Insert(i, value) (not Add). Also note was right that your bool[] b never changes; in C#, new bool[5] initializes all entries to false, so your available set will always start as 0..4 unless you flip some to true.

Two safe patterns here:

Backtrack in-place and re-insert at the original index before the next loop iteration.
Or, make fresh lists per call so parents remain untouched. That is simpler to reason about and avoids iterator invalidation. Example:

static void Permute(List<int> path, List<int> pool)
{
    if (pool.Count == 0)
    {
        Console.WriteLine(string.Join("->", path));
        return;
    }

    int n = pool.Count; // snapshot so changes in deeper calls do not affect this loop
    for (int i = 0; i < n; i++)
    {
        var nextPath = new List<int>(path) { pool[i] };
        var nextPool = new List<int>(pool);
        nextPool.RemoveAt(i);
        Permute(nextPath, nextPool);
    }
}

If you prefer in-place speed over allocations, use a swap-based permutation on an array instead. Either way, echoing , the recursive call happens before your un-do logic runs; you do reach those lines on unwind, but they must restore state exactly (same index) for the next branch to be correct.

All 9 Replies

DdoubleD 315 Posting Shark

17 Years Ago

It's not clear by your description what you want us to do. You provided some code, and some sort of description of what it does, but not whether you want it to do something different, or you are getting an error, etc.

Please clarify how you want to be helped.

DdoubleD 315 Posting Shark

17 Years Ago

Is this program throwing an exception? I did a walkthrough and noticed you are using b[i] , but you never assign/initialize values. Also, b[i] values never get changed/updated that I can tell, so the result is always the same.

for (int i = 0; i < 5; i++)
            {
                if (b[i] == false)
                {
                    available.Add(place[i]);
                }
            }

DdoubleD 315 Posting Shark

17 Years Ago

You are stuck in and endless loop because you keep adding to "available" following the recursive call. What is the objective here?

public void recursion(List<int> history, List<int> available)
        {
            if (available.Count == 0)
            {
                for (int i = 0; i < history.Count; i++)
                {
                    Console.Write(history[i].ToString() + "->");
                }
                Console.WriteLine(" ");
                return;
            }
            for (int i = 0; i < available.Count; i++)
            {
                history.Add(available[i]);
                available.RemoveAt(i);
                recursion(history, available);

                available.Add(history[history.Count - 1]);
                history.RemoveAt(history.Count - 1);



            }
            return;
        }

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

RehabReda 0 Light Poster · Answer 1 · 2009-08-26T19:37:24+00:00

It's not clear by your description what you want us to do. You provided some code, and some sort of description of what it does, but not whether you want it to do something different, or you are getting an error, etc.
Please clarify how you want to be helped.

thanks for ur reply
the problem is that i send a list in the parameters of recursive function
how (when i reach the end of recursion and go back ) the list remains as it is first time when i was in this function

the problem is that the list will be like the last update happened no what it must be in its recursive function

RehabReda 0 Light Poster · Answer 2 · 2009-08-26T20:21:19+00:00

RehabReda 0 Light Poster

17 Years Ago

no it didn't throw any exception

daveyb91 0 Newbie Poster · Answer 3 · 2009-08-26T20:54:26+00:00

You are stuck in and endless loop because you keep adding to "available" following the recursive call. What is the objective here?

public void recursion(List<int> history, List<int> available)
        {
            if (available.Count == 0)
            {
                for (int i = 0; i < history.Count; i++)
                {
                    Console.Write(history[i].ToString() + "->");
                }
                Console.WriteLine(" ");
                return;
            }
            for (int i = 0; i < available.Count; i++)
            {
                history.Add(available[i]);
                available.RemoveAt(i);
                recursion(history, available);

                available.Add(history[history.Count - 1]);
                history.RemoveAt(history.Count - 1);



            }
            return;
        }

I agree on that but, what I would like to add is, that you will never reach this bit:

available.Add(history[history.Count - 1]);
history.RemoveAt(history.Count - 1);

because you call your recursion function before these two lines are executed. So in order to fix this, you need to call your recursion function after the lines.

DdoubleD 315 Posting Shark · Answer 4 · 2009-08-26T21:04:59+00:00

I agree on that but, what I would like to add is, that you will never reach this bit:
available.Add(history[history.Count - 1]);
history.RemoveAt(history.Count - 1);
because you call your recursion function before these two lines are executed. So in order to fix this, you need to call your recursion function after the lines.

That's funny, because I stepped over those lines several times in the debugger. I'd like to hear exactly what it is that is trying to be achieved in this method because I'm not convinced those last two lines need to be there at all.

RehabReda 0 Light Poster · Answer 5 · 2009-08-28T02:35:19+00:00

That's funny, because I stepped over those lines several times in the debugger. I'd like to hear exactly what it is that is trying to be achieved in this method because I'm not convinced those last two lines need to be there at all.

thanks alot for ur help it is working now:)

DdoubleD 315 Posting Shark · Answer 6 · 2009-08-28T03:43:25+00:00

DdoubleD 315 Posting Shark

17 Years Ago

Anytime. Please mark the thread as solved.

List and recursion

Dani AI

Recommended Answers Collapse Answers

All 9 Replies

Recommended Answers