Pls explain how it works...

[iflash]

Hi,

This is a program from my book. But no matter how i look at it i jsut couldn't figure out how it works. I think the purpose of it is to reverse the order of an array of numbers. But if possible, pls explain the program line by line, it's very short. But skip lines like #include and int main(). Thnx in advance.



#include <stdio.h>
#define SIZE 10

void someFunction( const int [], int );

int main()
{
int a[ SIZE ] = { 8, 3, 1, 2, 6, 0, 9, 7, 4, 5 };

printf( "Answer is:\n" );
someFunction( a, SIZE );
printf( "\n" );
return 0;
}

void someFunction( const int b[], int size )
{
if ( size > 0 ) {
someFunction( &b[ 1 ], size - 1 );
printf( "%d ", b[ 0 ] );
}
}



Output of the program is attached.

[jim mcnamara]

Goofy program...


#include <stdio.h> use the file & screen i/o modules
#define SIZE 10 the word SIZE becomes 10 everywhere below

void someFunction( const int [], int ); function prototype for someFunction

int main()
{
int a[ SIZE ] = { 8, 3, 1, 2, 6, 0, 9, 7, 4, 5 }; this makes an array
of integers with SIZE elements

printf( "Answer is:\n" ); Display "Answer is:"
someFunction( a, SIZE ); call recursive function
printf( "\n" ); Line feed to the screen
return 0; quit
}

void someFunction( const int b[], int size )
the arguments are: the FIRST element of the array, number of elements in the array
{
if ( size > 0 ) { if the number of elements is more than zero
someFunction( &b[ 1 ], size - 1 ); call this same function
faking the FIRST element of the array with the second element of the array, and faking a smaller size for the aaray
printf( "%d ", b[ 0 ] ); print the first element of the array
}
}

[jim mcnamara]

What this code does is to create different versions of where the array starts,, park that information on the stack, and do it until it runs out of elements.

Then it unwinds the stack: going backwards, each first element
was the one that was passed origianlly to the function, but it ain't the same one. Since we are going backwards thru the stack
we get the elements in reverse order.

What this shows you is that a function and all of it's agrument gets pushed onto the stack (remembered) and when you pull it off the stack (recall what was remembered)you take a time trip backwards to the point in time when the function was first called.

It's an asinine alogrithm for production, but it's great for teaching about how functions work to store themselves on the stack.

[iflash]

if the function keeps calling itself, then by theory the line


printf( "%d ", b[ 0 ] );


will never be executed?

[jim mcnamara]

No.

The program pushes the code onto the stack RIGHT at the point where the function got called. When it comes back it pops the code off the stack, then goes to the printf.

If it weren't doing the printf what else would print the numbers you see?

[CornedBee]

Simpler program using the same mechanism:

0 #include <stdio.h>
1
2 void MyFunc(int);
3
4 int main()
5 {
6 int i;
7 printf("Enter a number:");
8 scanf("%i", &i);
9 printf("Numbers from 1 to %i:\n", i);
10 MyFunc(i);
11 printf("\nThat ends the demonstration.\n");
12 return 0;
13 }
14
15 void MyFunc(int i)
16 {
17 if(i > 0)
18 {
19 MyFunc(i - 1);
20 printf("%i", i);
21 }
22 }

This is tested, but remove the line numbers.

Ok, let's see what it does.
Instruction. (Lines)[function] Explanation
1. (6-9)[main] It asks you for a number and does some stupid output.
2. (10)[main] It calls MyFunc with the number (say 5)
3. (17)[MyFunc(5)] 5 != 0
4. (19)[MyFunc(5)] It calls MyFunc(4)
5. (17)[MyFunc(4)] 4 != 0
6. (19)[MyFunc(4)] It calls MyFunc(3)
7. (17)[MyFunc(3)] 3 != 0
8. (19)[MyFunc(3)] It calls MyFunc(2)
9. (17)[MyFunc(2)] 2 != 0
10. (19)[MyFunc(2)] It calls MyFunc(1)
11. (17)[MyFunc(1)] 1 != 0
12. (19)[MyFunc(1)] It calls MyFunc(0)
13. (17)[MyFunc(0)] 0 == 0
14. (22)[MyFunc(0)] It returns
15. (20)[MyFunc(1)] It prints 1
16. (22)[MyFunc(1)] It returns
17. (20)[MyFunc(2)] It prints 2
18. (22)[MyFunc(2)] It returns
19. (20)[MyFunc(3)] It prints 3
20. (22)[MyFunc(3)] It returns
21. (20)[MyFunc(4)] It prints 4
22. (22)[MyFunc(4)] It returns
23. (20)[MyFunc(5)] It prints 5
24. (22)[MyFunc(5)] It returns
25. (11)[main] More stupid output.
26. (12)[main] It returns and ends the program.

I've written in the round brackets the line number of the executed instructions and in the others the function with parameters. This shows nicely how the function is first called often and then how it unwinds and returns each function.

[CornedBee]

The highest number I could enter without a stack overflow was 64857.