Simple Recursion Question

[steveh44]

Hello,
I'm playing around with recursive loops in order to better understand how to iterate though directories. I've used the .Net methods 'GetDirectories("*.*", SearchOption.AllDirectories)' in 'foreach' loops to iterate through the file system but many examples i've seen use recursion techniques to do the same thing. So knowing nothing of recursion I wrote the following method which should simply count to 10 to see how it works.

public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}

static int value;
static int total;

private void Form1_Load(object sender, EventArgs e)
{
value = 1;
total = Recursion(value);
textBox1.Text += "The Total = " + total;
}

static int Recursion(int x)
{
if (x <= 10)
{
x++;
Recursion(x);
}
return x;
}
}

I assumed that the method 'Recursion(int x)' would return the value '10' to 'total' but it always returns a value of '2'. I stepped through with the debugger in VS2008 express and all goes well until 'x=10' but the method continues to loop and actually counts down before returning '2'.

Can anyone please explain what i'm doing wrong here as i've spent several hours scratching my head over this one.

Cheers

SteveH

[kvprajapati]

Read 1. http://en.wikipedia.org/wiki/Recursion 2. http://en.wikipedia.org/wiki/Recursion_%28computer_science%29

[finito]

I havn't touched recursion since I learned it
Thanks for giving me a chance to recap:

public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

         int value;
         int total;

        private void Form1_Load(object sender, EventArgs e)
        {
            value = 1;
            total = Recursion(value);
            textBox1.Text += "The Total = " + total;
        }

        static int Recursion(int x)
        {

            while (x <= 10)
                x =Recursion(x+1);
            
            return x;
        }
    }

You may want to change the value to equal 0; to get 10.

if you wnat your code then:

public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        static int value;
        static int total;

        private void Form1_Load(object sender, EventArgs e)
        {
            value = 1;
            total = Recursion(value);
            textBox1.Text += "The Total = " + total;
        }

        static int Recursion(int x)
        {
            if (x <= 10)
            {
                x++;
                x=Recursion(x);
            }
            return x;
        }
    }

This is the only think I changed

x=Recursion(x);

Enjoy

[apegram]

Here's a recursive function I recently wrote to go through a set of folders and subfolders to rename images (they had a .jpeg extension, needed to just be .jpg).

string path = @"Q:\some_company\some_path\";

Action<string> fileRenamer = null;
fileRenamer = directoryPath =>
{
    string[] files = Directory.GetFiles(directoryPath, "*.jpeg");
    foreach (string file in files)
    {
        string newFile = file.Replace(".jpeg", ".jpg");
        if (!File.Exists(newFile))
            File.Move(file, newFile);
    }

    string[] directories = Directory.GetDirectories(directoryPath);
    foreach (string dir in directories)
        fileRenamer(dir);
};

fileRenamer(path);
Console.WriteLine("done");

[finito]

Nice one apegram, that would is useful to me. I was just working on something like that. You sped things up.

The most random thing :)
Thanks.

[steveh44]

Thanks to everyone for the examples. When I set breakpoints in the code the locals and call stack windows show the value of 'x' counting up from 1-10 and counting down 10-1. Obviously I dont understand something here. Recursion is not as intuitive as iteration.

[finito]

During Recursion You are calling on stacks.
So everytime 1 is added a new stack is called.
When the last stack is reached, it comes back out of each stack making x equal to what it was when it entered

Stack 1 X= 0++
Stack 2 X= 1++
....
....
Stack 10 X = 9++

Now it will go back the way it came.

But if you make X = the recursion that makes it static.

Please mark as solved if it is.

[Sodabread]

As said by a shirt on ThinkGeek, In order to understand recursion, one must understand recursion.

Honestly, I think it's much easier to explain in pseudo code than actual code.

Directory dir = <location>
call renameFilesInDir(dir)

function renameFilesInDir(Directory dir)
    
    foreach(file f in dir)
        rename file

    foreach(directory d in Dir)
        renameFilesInDir(dir)

end

The directory ("C:\" as an example) is created, sending that down into a function. The function does its renames the files, then calls itself for each directory in the root directory. The subsequent call(s) treats the passed in dir (let's use "C:\Windows") as the root, then loops through that entire directory, performing the same exact steps; it renames the files, then calls the function once again for each directory that is in C:\Windows.

In this example, the function will continue to do this until it gets into a folder which has no more folders, so the renameFilesInDir function is not called, the function goes back to the previous call and calls the function again for the next Directory in dir.

Call 1:
dir = C:\

Call 2 (from C:\):
dir = C:\Documents and Settings\

Call 3 (from C:\Documents and Settings\)
dir = C:\Documents and Settings\User 1\

No directories in User 1
Fall back to Call 2

Call 3 (from C:\Documents and Settings\)
dir = C:\Documents and Settings\User 2\

No directories in User 2
Fall back to Call 2

No more directories in Documents and Settings
Fall back to Call 1

Call 2 (from C:\)
dir = C:\Directory 2\

...

Recursion is one of the most difficult concepts to grasp in code, or at least I thought so when I started coding, so don't worry if you don't totally get it yet. It takes time.

I hope this post helps you out a little.

[steveh44]

Recursion certainly is much more complicated than I thought. I'll knuckle down and try to grasp the technique. I'm new to C# and this style of programming. The tutorials and textbooks i've read so far don't even mention it. I suppose you could use conditional loops for iteration to do the same thing as recursion. But I feel its something I should try to understand (along with Delegates) if i'm ever going progress.

[finito]

As said by a shirt on ThinkGeek, In order to understand recursion, one must understand recursion.

Honestly, I think it's much easier to explain in pseudo code than actual code.

Directory dir = <location>
call renameFilesInDir(dir)

function renameFilesInDir(Directory dir)
    
    foreach(file f in dir)
        rename file

    foreach(directory d in Dir)
        renameFilesInDir(dir)

end

The directory ("C:\" as an example) is created, sending that down into a function. The function does its renames the files, then calls itself for each directory in the root directory. The subsequent call(s) treats the passed in dir (let's use "C:\Windows") as the root, then loops through that entire directory, performing the same exact steps; it renames the files, then calls the function once again for each directory that is in C:\Windows.

In this example, the function will continue to do this until it gets into a folder which has no more folders, so the renameFilesInDir function is not called, the function goes back to the previous call and calls the function again for the next Directory in dir.

Call 1:
dir = C:\

Call 2 (from C:\):
dir = C:\Documents and Settings\

Call 3 (from C:\Documents and Settings\)
dir = C:\Documents and Settings\User 1\

No directories in User 1
Fall back to Call 2

Call 3 (from C:\Documents and Settings\)
dir = C:\Documents and Settings\User 2\

No directories in User 2
Fall back to Call 2

No more directories in Documents and Settings
Fall back to Call 1

Call 2 (from C:\)
dir = C:\Directory 2\

...

Recursion is one of the most difficult concepts to grasp in code, or at least I thought so when I started coding, so don't worry if you don't totally get it yet. It takes time.

I hope this post helps you out a little.

SodaBread in your Defence that isn't the most easiest code to explain.

Lets take you original code.

Look at attachment

Now when you make X= Recursion(X);
X is Redifined when the stack is returned because X= is left waiting until it is done. So when You return X; the new value is returned.

Hope this makes sense.

[steveh44]

Recursion has really got me thinking ! I'm now using the Watch, Locals ans Call Stack windows together and seeing more 'behind the scenes'.
A light came on in my head and it's beginning to become clearer.
Many thanks for the advice and examples given.

[finito]

glad to have helped someone understand recursion can you please mark as solved.

Thanks

[Sodabread]

SodaBread in your Defence that isn't the most easiest code to explain.

Lets take you original code.

Look at attachment

Now when you make X= Recursion(X);
X is Redifined when the stack is returned because X= is left waiting until it is done. So when You return X; the new value is returned.

Hope this makes sense.

Maybe not, but I was trying to explain it in the sense of what he's actually trying to accomplish.