Need explanation on recursive functions?

closed account (3UMLy60M)
Hello all,

Can someone please explain to me how calling m3(3, 4) causes 81 to be the output of the following recursive function?

1
2
3
4
5
6
7
 
int m3 (int a, int b)
{
    if (b == 0)
        return 1;
    else
        return a * m3(a, b - 1);
}

And also, why is the output here 12 when m2(3, 4) is called?

1
2
3
4
5
6
7
 
int m2(int a, int b)
{
    if (a == 0)
        return 0;
    else
        return a * m2(a - 1, b);
}


Thanks!
Last edited on
Smac89 (1727)
m2:

Breakpoint 2, m2 (a=3, b=4) at cap.cc:13
13	   if (a == 0)
(gdb) display a
1: a = 3
(gdb) display b
2: b = 4
(gdb) n
16	      return a * m2(a - 1, b);
2: b = 4
1: a = 3
(gdb) 

Breakpoint 2, m2 (a=2, b=4) at cap.cc:13
13	   if (a == 0)
2: b = 4
1: a = 2
(gdb) 
16	      return a * m2(a - 1, b);
2: b = 4
1: a = 2
(gdb) 

Breakpoint 2, m2 (a=1, b=4) at cap.cc:13
13	   if (a == 0)
2: b = 4
1: a = 1
(gdb) 
16	      return a * m2(a - 1, b);
2: b = 4
1: a = 1
(gdb) 

Breakpoint 2, m2 (a=0, b=4) at cap.cc:13
13	   if (a == 0)
2: b = 4
1: a = 0
(gdb) 
14	      return 0;
2: b = 4
1: a = 0
(gdb) 
17	}
2: b = 4
1: a = 0
(gdb) 
17	}
2: b = 4
1: a = 1
(gdb) 
17	}
2: b = 4
1: a = 2
(gdb) 
17	}
2: b = 4
1: a = 3
(gdb)


m3:

Breakpoint 1, m3 (a=3, b=4) at cap.cc:5
5	   if (b == 0)
8	      return a * m3(a, b - 1);
(gdb) display a
3: a = 3
(gdb) display b
4: b = 4
(gdb) n

Breakpoint 1, m3 (a=3, b=3) at cap.cc:5
5	   if (b == 0)
4: b = 3
3: a = 3
(gdb) 
8	      return a * m3(a, b - 1);
4: b = 3
3: a = 3
(gdb) 

Breakpoint 1, m3 (a=3, b=2) at cap.cc:5
5	   if (b == 0)
4: b = 2
3: a = 3
(gdb) 
8	      return a * m3(a, b - 1);
4: b = 2
3: a = 3
(gdb) 

Breakpoint 1, m3 (a=3, b=1) at cap.cc:5
5	   if (b == 0)
4: b = 1
3: a = 3
(gdb) 
8	      return a * m3(a, b - 1);
4: b = 1
3: a = 3
(gdb) 

Breakpoint 1, m3 (a=3, b=0) at cap.cc:5
5	   if (b == 0)
4: b = 0
3: a = 3
(gdb) 
6	      return 1;
4: b = 0
3: a = 3
(gdb) 
9	}
4: b = 0
3: a = 3
(gdb) 
9	}
4: b = 1
3: a = 3
(gdb) 
9	}
4: b = 2
3: a = 3
(gdb) 
9	}
4: b = 3
3: a = 3
(gdb) 
9	}
4: b = 4
3: a = 3
(gdb) 
81 0


m2 returns 0, not 12 and m3 returns 81

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#include <cstdio>

int m3 (int a, int b)
{
   if (b == 0)
      return 1;
   else
      return a * m3(a, b - 1);
}

int m2(int a, int b)
{
   if (a == 0)
      return 0;
   else
      return a * m2(a - 1, b);
}

int main()
{   
   printf("%d %d\n", m3(3,4), m2(3,4));
   
   return 0;
}
Last edited on
closed account (3UMLy60M)
I don't understand this code.
vlad from moscow (6539)
It is obvious that function m2 has a typo

1
2
3
4
5
6
7
 
int m2(int a, int b)
{
    if (a == 0)
        return 0;
    else
        return a * m2(a - 1, b);
}


It always will return 0.

I think you meant plus instead of multiplier

1
2
3
4
5
6
7
 
int m2(int a, int b)
{
    if (a == 0)
        return 0;
    else
        return a + m2(a - 1, b);
}

Topic archived. No new replies allowed.