How this recursive function works in langage C?-CodePudding

I'm using online debugger to try to understand, how it works but it is not clear.

https://www.onlinegdb.com/online_c_compiler

The code:

#include <stdio.h>

unsigned int plus(unsigned int x, unsigned int y){
  return x y;
}

unsigned int schema (unsigned int x, unsigned int y, unsigned int a, unsigned int (*f)(unsigned int, unsigned int)){
    return((y==0)?a:(*f)(schema(x,y-1,a,f),x));
}

unsigned int prod(unsigned int x, unsigned int y){
    return(schema(x,y,0,plus));
}

int main()
{
    int m,n;
    
    printf("Donner deux nombres ? : ");
    scanf("%d %d", &m, &n);
    printf("%d * %d = %d\n", m, n, prod(m,n));

    return 0;
}

How does the schema function to calls plus function with the correct parameters ?

The code is here : https://onlinegdb.com/nAglj8NwZr

Here the debug :

Reading symbols from a.out...
(gdb) run
Starting program: /home/a.out 
Donner deux nombres ? : 3 2

Breakpoint 2, prod (x=21845, y=1431655088) at main.c:20
20      unsigned int prod(unsigned int x, unsigned int y){
(gdb) step

Breakpoint 1, prod (x=3, y=2) at main.c:21
21          return(schema(x,y,0,plus));
(gdb) step

Breakpoint 4, schema (x=32767, y=4294962119, a=0, f=0xf0b5ff) at main.c:16
16      unsigned int schema (unsigned int x, unsigned int y, unsigned int a, unsigned int (*f)(unsigned int, unsigned int)){
(gdb) step

Breakpoint 3, schema (x=3, y=2, a=0, f=0x555555555189 <plus>) at main.c:17
17          return((y==0)?a:(*f)(schema(x,y-1,a,f),x));
(gdb) step

Breakpoint 4, schema (x=0, y=0, a=0, f=0x0) at main.c:16
16      unsigned int schema (unsigned int x, unsigned int y, unsigned int a, unsigned int (*f)(unsigned int, unsigned int)){
(gdb) step

Breakpoint 3, schema (x=3, y=1, a=0, f=0x555555555189 <plus>) at main.c:17
17          return((y==0)?a:(*f)(schema(x,y-1,a,f),x));
(gdb) step

Breakpoint 4, schema (x=0, y=24, a=0, f=0x0) at main.c:16
16      unsigned int schema (unsigned int x, unsigned int y, unsigned int a, unsigned int (*f)(unsigned int, unsigned int)){
(gdb) step

Breakpoint 3, schema (x=3, y=0, a=0, f=0x555555555189 <plus>) at main.c:17
17          return((y==0)?a:(*f)(schema(x,y-1,a,f),x));
(gdb) step
18      }
(gdb) step

Breakpoint 6, plus (x=3, y=0) at main.c:12
12      unsigned int plus(unsigned int x, unsigned int y){
(gdb) step

Breakpoint 5, plus (x=0, y=3) at main.c:13
13          return x y;
(gdb) step
14      }
(gdb) step
schema (x=3, y=1, a=0, f=0x555555555189 <plus>) at main.c:18
18      }
(gdb) step

Breakpoint 6, plus (x=3, y=1) at main.c:12
12      unsigned int plus(unsigned int x, unsigned int y){
(gdb) step

Breakpoint 5, plus (x=3, y=3) at main.c:13
13          return x y;
(gdb) step
14      }
(gdb) step
schema (x=3, y=2, a=0, f=0x555555555189 <plus>) at main.c:18
18      }
(gdb) step
prod (x=3, y=2) at main.c:22
22      }
(gdb) step
__printf (format=0x555555556023 "%d * %d = %d\n") at printf.c:28
28      printf.c: No such file or directory.
(gdb) continue
Continuing.
3 * 2 = 6
[Inferior 1 (process 2233) exited normally]
(gdb)

Thanks a lot if someboby could explain this code.

CodePudding user response：

Consider providing 4 and 5 to your program. Perhaps this will help you to visualize the recursion.

prod(4, 5)
schema(4, 5, 0, plus)
plus(schema(4, 5-1, 0, plus), 4)
plus(plus(schema(4, 4-1, 0, plus), 4), 4)
plus(plus(plus(schema(4, 3-1, 0, plus), 4), 4), 4)
plus(plus(plus(plus(schema(4, 2-1, 0, plus), 4), 4), 4), 4)
plus(plus(plus(plus(plus(schema(4, 1-1, 0, plus), 4), 4), 4), 4), 4)
plus(plus(plus(plus(plus(0, 4), 4), 4), 4), 4)
plus(plus(plus(plus(4, 4), 4), 4), 4)
plus(plus(plus(8, 4), 4), 4)
plus(plus(12, 4), 4)
plus(16, 4)
20

Note that because prod only calls another function, tail-call optimization may take place. However, schema calls itself, and then feed the result to the function pointer provided, so those stack frames have to remain, meaning TCO cannot be performed.

If, however, you were dealing with a sightly smarter schema function, which used that a parameter usefully as an updating accumulator, TCO would be possible.

unsigned int schema(unsigned int x, unsigned int y, unsigned int a, 
                    unsigned int (*f)(unsigned int, unsigned int)) {
    if (y == 0) return a;

    return schema(x, y-1, f(x, a), f);
}