Recursion Question C language

Get Started
1

Hi

I would like some help understanding the following code :

#include <stdio.h>
int func(int z, char a);
int main(void)
{
func(4,'a');
} // end main
int func(int z, char a)
{
 if (z==1)
 {
  printf("%s", "last\n");
  return 1;
 } // end if
 func(z-1,a);
 printf("%d\n", z,a);
} // end func

The output is:
last
2
3
4

However, if you put the last printf above the last recursive function call, the output is

4
3
2
last

Why the reversal?

In the first instance, I can understand that the number 4 passed to the function (func) is then repeatedly reduced when the recursion calls itself (z-1) until it reaches ‘last’ and then prints the output below.

But, where does the 2 come from?

If someone could help me trace the four through the various functions I would be most grateful.

thx!
Karen

2

Because when the print statement is above the function call, it prints and then calls the function:

call function with ‘4’. print ‘4’ ; call function with ‘3’, print ‘3’, call function with ‘2’, print ‘2’, call function with ‘1’, print ‘last’, return, return, return, return

And when the print statement is below the function call, it calls the function recursively, until z becomes 1, and then returns back to each previous call and prints the z value of that call :

call function with ‘4’, call function with ‘3’, call function with ‘2’, call function with ‘1’; print ‘last’, return, print ‘2’, return, print ‘3’, return, print ‘4’, return

2 Likes
3

Wow! That is so cool!

Thanks for the great explanation :slight_smile:

4

Ok, but if you put the function statement both above and below the printf statement (i.e. the printf statement “sandwiched” between them. You get the following output:

last
2
last
3
last
2
last
4
last
2
last
3
last
2

Which does not follow your logic above? Why all the bizarre mix?

ps - I am running a little deeply into recursion with these simple examples as I really want to get my head around it.

Tx
Karen

5

You changed the logic :wink:

call proc with '4'
    call proc with '3'
        call proc with '2'
            call proc with '1'
                print 'last'
                return
            print '2'
            call proc with '1'
                print 'last'
                return
            return
        print '3'
        call proc with '2'
            call proc with '1'
                print 'last'
                return
            print '2'
            call proc with '1'
                print 'last'
                return
            return      
        return
    print '4'
    call proc with '3'
        call proc with '2'

Etc etc.

1 Like
6

Thanks!

Working through it now…

7

Check out this [code visualization tool](http://pythontutor.com/c.html#code=%23include+<stdio.h> int+func(int+z,+char+a)%3B int+main(void) { func(4,‘a’)%3B }+//+end+main int+func(int+z,+char+a) { +if+(z%3D%3D1) +{ ++printf(“%25s”,+“last\n”)%3B ++return+1%3B +}+//+end+if +func(z-1,a)%3B +printf(“%25d\n”,+z,a)%3B }+//+end+func&mode=display&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&textReferences=false&py=c&rawInputLstJSON=[]&curInstr=0). Click “forward” to step through your code.

2 Likes
8

Hey!

That’s really neat :slight_smile:

Thanks for that link. I am now messing with the Towers of Hanoi problem. Lots of fun!

Karen

9

This topic was automatically closed 91 days after the last reply. New replies are no longer allowed.