列出下列函数 foo(2，7)的递归调用过程

Question

void foo(int m, int n) { if(n = =0) return 1; if(n%2 = =1) return (foo(m*m,n/2)*m);return (foo(m*m,n/2));}

Answer 1

第一次执行foo m=2 n=7 满足if(n%2==1)语句 执行到 return foo(4,3)*2;
第二次执行foo m=4, n=3 满足if(n%2==1)语句 执行到 return foo(16,1)*4;
第三次执行foo m=16,n=1满足if(n%2==1)语句 执行到 return foo(256,0)*16
第四次执行foo m=256,n=0, 返回1；
所以第三次函数执行结果为1*16；
第二次执行结果为16*4;
第一次执行结果为 64*2=128;

Answer 2

首先第1层，m=2 n=7 n%2 = =1成立执行foo(m*m,n/2)*m也就是foo(4, 3)*2
第2层，m=4 n=3 n%2 = =1成立执行foo(m*m,n/2)*m也就是foo(16, 1)*4
第3层，m=16 n=1 n%2 = =1成立执行foo(m*m,n/2)*m也就是foo(256, 0)*16
第4层，m=256 n=0 n = =0成立执行返回1
回到第3层，计算1*16，返回16
回到第2层，计算16*4，返回64
回到第1层，计算64*2，返回128
最终结果就是128
不过你的foo返回值写错了，不是void，应该是int

Answer 3

n = =0是这个递归函数的出口

递归就相当于进栈出栈的过程，先进后出
f(2, 7) = f(4, 3) * 2 = (f(16, 1) *4 ) * 2 = ( (f(256, 0) * 16)*4)*2 = 1*16*4*2 = 128

栈结构如下
1
f(256, 0) * 16
f(16, 1) *4
f(4, 3) * 2
f(2, 7)