Extremely frustrating C program

[mathrocks]

I'll be extremely happy if anyone can tell me how the following program works. I understand that it prints the numbers in the array in reverse order, but I have no idea how it does this. It enters the if statement with startIndex=0, calls someFunction again and increases it by one until it hits 10 and exits and prints b[10] but doesn't it keep going through the loop with startIndex=0 and going up until it hits 10?? I don't see how it can decrease and print b[9]...down to b[0]??

Any help would be appreciated




#include <stdio.h>
#define SIZE 10

/* function prototype */
void someFunction( const int b[], int startIndex, int size );

/* function main begins program execution */
int main()
{
int a[ SIZE ] = { 8, 3, 1, 2, 6, 0, 9, 7, 4, 5 }; /* initialize a */

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

return 0; /* indicates successful termination */

} /* end main */

/* What does this function do? */
void someFunction( const int b[], int startIndex, int size )
{
if ( startIndex < size ) {
someFunction( b, startIndex + 1, size );
printf( "%d ", b[ startIndex ] );
} /* end if */

} /* end function someFunction */

 

[TenNen]

Change your program into something like this, things will turn around...
#include <stdio.h>
#define SIZE 10

/* function prototype */
void someFunction( const int b[], int startIndex, int size );

/* function main begins program execution */
int main()
{
int a[ SIZE ] = { 8, 3, 1, 2, 6, 0, 9, 7, 4, 5 }; /* initialize a */

printf( "Answer is:\n" );
someFunction( a, SIZE-1,0 );
printf( "\n" );

return 0; /* indicates successful termination */

} /* end main */

/* What does this function do? */
void someFunction( const int b[], int startIndex, int size )
{
if ( startIndex > =size ) {
printf( "%d ", b[ startIndex ] );
someFunction( b, startIndex - 1, size );

} /* end if */

} /* end function someFunction */

 

[mathrocks]

Change your program into something like this, things will turn around...
#include <stdio.h>
#define SIZE 10

/* function prototype */
void someFunction( const int b[], int startIndex, int size );

/* function main begins program execution */
int main()
{
int a[ SIZE ] = { 8, 3, 1, 2, 6, 0, 9, 7, 4, 5 }; /* initialize a */

printf( "Answer is:\n" );
someFunction( a, SIZE-1,0 );
printf( "\n" );

return 0; /* indicates successful termination */

} /* end main */

/* What does this function do? */
void someFunction( const int b[], int startIndex, int size )
{
if ( startIndex > =size ) {
printf( "%d ", b[ startIndex ] );
someFunction( b, startIndex - 1, size );

} /* end if */

} /* end function someFunction */

The problem is why does it print the numbers in reverse order. The book gives me that exact code I had and asks "What does this function do?" I don't know what makes it reverse the array. I'm not asking to fix it so it prints regular.

Thanks though.

 

[Anteros]

Think about what happens sequentially in the code and figure out when the first printf() is hit. The best way to visualize recursion like this is to write down the recursive function calls with arguments.

So...
somefunction(a, 0, 10)
somefunction(a, 1, 10)
somefunction(a, 2, 10)
...

Has a print been hit yet? What function call are you in when the first printf() is hit?

You'll get the hang of recursion eventually. If you need more help, just post back

 

[mathrocks]

Think about what happens sequentially in the code and figure out when the first printf() is hit. The best way to visualize recursion like this is to write down the recursive function calls with arguments.

So...
somefunction(a, 0, 10)
somefunction(a, 1, 10)
somefunction(a, 2, 10)
...

Has a print been hit yet? What function call are you in when the first printf() is hit?

You'll get the hang of recursion eventually. If you need more help, just post back

Doesn't the printf statement execute when you are at somefunction(a,10,10)? So it will print out the last number in the array first but what I'm stuck on is how does it continue to decrease when it will always increase by 1 and print when it hits 10??

 

[TenNen]

Sorry, i didn't read your post carefuly and didn't test your code either. But I don't know how to answer. bad as i am !

 

[Anteros]

Doesn't the printf statement execute when you are at somefunction(a,10,10)? So it will print out the last number in the array first but what I'm stuck on is how does it continue to decrease when it will always increase by 1 and print when it hits 10??

somefunction(a, 9, 10)
..somefunction(a, 10, 10) <- will this call somefunction() or print anything?

Since somefunction(a, 10, 10) doesn't pass the conditional if statement it returns and breaks the recursion. Now what happens? Which function call are you in now?

In other words, somefunction(a, 9, 10) called somefunction(a, 10, 10) which returned so now it needs to execute the next line of code which is the printf(). Then somefunction(a, 9, 10) returns and now we're in somefunction(a, 8, 10). The recursion then flows down the stack and you get an array printed out in reverse order.

 

[Anteros]

Also, the example TenNen referred to is a good one. What happens if you reverse the order of the printf() and somefunction() calls.

i.e.

printf( "%d ", b[ startIndex ] );
someFunction( b, startIndex + 1, size );

Now you have something like this (simplified)

printf(0)
somefunction(a, 1, 10)
printf(1)
somefunction(a, 2, 10)
...

whereas in your original case we had something like this

somefunction(a, 1, 10)
somefunction(a, 2, 10)
... (a bunch more somefunction() calls)
somefunction(a, 10, 10)
printf(9)
printf(8)
... (a bunch more printf() calls)
printf(0)

 

[mathrocks]

somefunction(a, 9, 10)
..somefunction(a, 10, 10) <- will this call somefunction() or print anything?

Since somefunction(a, 10, 10) doesn't pass the conditional if statement it returns and breaks the recursion. Now what happens? Which function call are you in now?

In other words, somefunction(a, 9, 10) called somefunction(a, 10, 10) which returned so now it needs to execute the next line of code which is the printf(). Then somefunction(a, 9, 10) returns and now we're in somefunction(a, 8, 10). The recursion then flows down the stack and you get an array printed out in reverse order.

Ok, maybe I'm not really understanding recursion. I understand that it breaks out of somefunction at (a,10,10) but what causes it to go down to (a,9,10) and finally (a,0,10)? Is this some rule about recursion I missed? There is nothing in the code about decreasing the numbers.
Or does the recursion function keep all the values that meets the condition in memory and returns them at the end? I'm having trouble seeing the logic.

Thanks a lot for your help!

 

[Anteros]

Ok, maybe I'm not really understanding recursion. I understand that it breaks out of somefunction at (a,10,10) but what causes it to go down to (a,9,10) and finally (a,0,10)? Is this some rule about recursion I am missed? There is nothing in the code about decreasing the numbers.

It doesn't "break out" of somefunction(), that invocation of somefunction simply returns. And the point at which it returns is right after the point at which it was called. You have to think about it step by step. Try thinking about it this way. Each line is a single step in the program execution.

0. somefunction(a, 0, 10) <- The first function is called

1. if statement
2. *
3. printf() called (if we are inside if statement)

4. printf( "\n" );

This block of code occurs every time you make a call to somefunction(). The trick is that what I denoted by * is actually another call to somefunction() in which this same block of code is executed. When the last element in the array is printed, you still have to go through all of the other lines of code.

Say there were only 2 elements in the array. Your program execution would occur in this order (0, 1, 2, 1, 2, 1 *at this point the if statement fails*, 3, 3, 4). The elements of the array are printed out at step 3.

Remeber, a program is sequential. Everything happens in order. Just don't forget that once you enter a function, even if you call some other function you'll still come back to that function. What if you called someotherfunction(a, 0, 10) inside of somefunction(). I think it's clear that you would just execute that function and then come back to somefunction(). There is absolutely no difference when you are calling the same function. It's just a special case and it's called recursion.

 

[mathrocks]

It doesn't "break out" of somefunction(), that invocation of somefunction simply returns. And the point at which it returns is right after the point at which it was called. You have to think about it step by step. Try thinking about it this way. Each line is a single step in the program execution.

0. somefunction(a, 0, 10) <- The first function is called

1. if statement
2. *
3. printf() called (if we are inside if statement)

4. printf( "\n" );

This block of code occurs every time you make a call to somefunction(). The trick is that what I denoted by * is actually another call to somefunction() in which this same block of code is executed. When the last element in the array is printed, you still have to go through all of the other lines of code.

Say there were only 2 elements in the array. Your program execution would occur in this order (0, 1, 2, 1, 2, 1 *at this point the if statement fails*, 3, 3, 4). The elements of the array are printed out at step 3.

Remeber, a program is sequential. Everything happens in order. Just don't forget that once you enter a function, even if you call some other function you'll still come back to that function. What if you called someotherfunction(a, 0, 10) inside of somefunction(). I think it's clear that you would just execute that function and then come back to somefunction(). There is absolutely no difference when you are calling the same function. It's just a special case and it's called recursion.

Ok, I think I'm starting to understand this. Let me know if I'm correct or not.

if(0)
.if(1)
..if(2)
...if(3)
...if(4)
...if(5)
...if(6)
...if(7)
...if(8)
...if(9)
...if(10)* breaks out of this if statement, so printf(10) isn't executed
...printf(10)
...printf(9)
...printf(8)
...printf(7)
...printf(6)
...printf(5)
...printf(4)
...printf(3)
..printf(2)
.printf(1)
printf(0)

Are the values just in memory for each if statement? Like when it goes to (a,4,10) it remembers (a,3,10) was in "this if statement" and (a,2,10) was in "this if statement"...

 

[Anteros]

Yes, I suppose you could think of it that way. All of the local variables in a function are kept on the stack (in memory) until they go out of scope. So in this case, startindex is 0 in the 1st call to somefunction(), 1 in the 2nd call to somefunction(), etc. When the 2nd call to somefunction() returns back into the 1st call, the value of startindex is "remembered" and used in the remainder of the function. This only occurs though if it's a local variable/argument. Think about the case where a recursive function modifies a global variable. If that happens, the recursive function won't "remember" the value of the global, it will simply use whatever was last set.

It sounds like you are understanding much better now. Your execution tree above looks right on with one tiny mistake. printf(10) is never executed. You have that in your comments so I know you understand but then you include printf(10) as your next call.

Recursion can be pretty tricky to wrap your mind when you first encounter it but eventually it will click.