How this recursive function works in langage C?

Question

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.

I would recommend rewriting the body of `schema` into an `if` + `else` section, that makes it a lot easier to read. Other than that my only guess at your confusion would be the function pointer syntax? — UnholySheep, Jun 27 '22 at 22:12
Welcome back to Stack Overflow. Please read [ask] and try to make your question more specific. It [is not possible](https://meta.stackoverflow.com/questions/278797) to explain how a bunch of code works in this format, because we have no way to know *why* you don't understand it already, *what* you don't understand about it, or *how* to express things in a way that would be clearer to you. — Karl Knechtel, Jun 27 '22 at 22:13
The `schema()` function recurses `n` times, and on the way back adds `m` to result each time it returns to the previous instance. The `a` is a bit of a red herring. it serves no role and at the top of the recursion the code might as well use `0` directly. — Weather Vane, Jun 27 '22 at 22:43
`return((y==0)?a:(*f)(schema(x,y-1,a,f),x));` is a lot easier to read when formatted nicely, and if we get rid of the extraneous parens. `return y == 0 ? a : f(schema(x, y-1, a, f), x);` — Chris, Jun 27 '22 at 22:48
@KarlKnechtel, yes sorry, I will try to be more clear. Thanks — Maykiwo GNO, Jun 28 '22 at 08:07

Chris · Accepted Answer · 2022-06-27T23:10:51.437

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);
}

I think the code is not optimize because it just only for an example how pointer function works. I found this code in the book, it is not mine. — Maykiwo GNO, Jun 28 '22 at 10:20

How this recursive function works in langage C?

1 Answers1