Help on thinking recursively?

[mikeblas]

Looking at code probably helps. Here's a Win32 program that will compile in VC++ and traverse all the directories on your C: drive. At each directory, it shows how much recursion it has done and how much stack space it is using.

On my machine, it finishes up with this result:

Max depth of 4136 bytes at C:\Program Files\Microsoft SQL Server\100\Setup Bootstrap\Update Cache\KB2285068\ServicePack\x64\setup\1033\pfiles\sqlservr\100\setup\release\x64\help\10
33\*.*
Max depth of 18 at C:\Program Files\Microsoft SQL Server\100\Setup Bootstrap\Update Cache\KB2285068\ServicePack\x64\setup\1033\pfiles\sqlservr\100\setup\release\x64\help\1033\*.*

The stack size calculation is actually a bit off because the compiler notices that the nHere variable isn't used concurrently with other variables inside the stack frame, and reuses that space. Or, it packs the stack aligning the large objects differently.

Point is, though, that even at 18 levels of directories, we only use about 4K of stack space. At each iteration, the only thing on the stack is the current search context and a buffer to create the string for the next deeper search pattern.

// Traverser.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#define _CRT_SECURE_NO_WARNINGS
#include <windows.h>
#include <stdio.h>
#include <tchar.h>

int nMaxDepth = 0;
ptrdiff_t nMaxDepthBytes = 0;
char szMaxDepthPlace[MAX_PATH];
char szMaxDepthBytesPlace[MAX_PATH];

void Traverse( LPCTSTR pstrPath, int *pBottom, int nDepth )
{
	WIN32_FIND_DATA sFindData;
	HANDLE h = FindFirstFile( pstrPath, &sFindData );
	char sz[MAX_PATH];
	int nHere = 0;
	if ( h != INVALID_HANDLE_VALUE )
	{
		do 
		{
			if ( sFindData.cFileName[0] == '.' )
			{
				if ( sFindData.cFileName[1] == 0 )
					continue;
				if ( sFindData.cFileName[1] == '.' && sFindData.cFileName[2] == 0 )
					continue;
			}

			nHere++;

			if ( sFindData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY )
			{
				// it's a directory!
				strcpy( sz, pstrPath );
				char *pstrWhack = strrchr( sz, '\\' );
				pstrWhack++;
				strcpy( pstrWhack, sFindData.cFileName );
				strcat( pstrWhack, "\\*.*" );
				Traverse( sz, pBottom, nDepth + 1 );
			}
		}
		while ( FindNextFile( h, &sFindData ) );
	}

	FindClose( h );

	ptrdiff_t nDepthBytes = pBottom - &nHere;
	printf( "%4d %6u - %s\n", nDepth, nDepthBytes, pstrPath );

	if ( nMaxDepthBytes < nDepthBytes )
	{
		nMaxDepthBytes = nDepthBytes;
		strcpy( szMaxDepthBytesPlace, pstrPath );
	}

	if ( nMaxDepth < nDepth )
	{
		nMaxDepth = nDepth;
		strcpy( szMaxDepthPlace, pstrPath );
	}

	return;
}


int _tmain(int argc, _TCHAR* argv[])
{
	int nBottom ;
	Traverse( "C:\\*.*", &nBottom, 0 );

	printf( "\n" );
	printf( "Max depth of %d bytes at %s\n", nMaxDepthBytes, szMaxDepthBytesPlace );
	printf( "Max depth of %d at %s\n", nMaxDepth, szMaxDepthPlace );

	return 0;
}