Please explain the logic behind this program that uses recursion to calculate a^b (a raised to power b)
c
Solution
The idea behind this recursion is, that ab = (a2)b/2, and ab = a(a2)(b-1)/2.
Depending on whether b is odd or even (thats the `n%2 == 1` part), you choose one of these formulas to ensure b/2 or (b-1)/2 is still an integer. Note here, that the `n/2` in your code actually is (n-1)/2 for odd n, since integer division rounds down automatically.
This recursion terminates since the exponent grows smaller with each step.
Problem
It's really embarrassing!!I just fail to understand the working of the following little program that uses recursion to calculate the powers of a number "a" ("a" raised to a power "b").Kindly explain the logic used behind this function.I don't understand the use of the "x*x" parameter,the n/2 parameter and the "n modulo 2" part.Please dissect it for me. ``` #include<stdio.h> int foo(int,int); int main() { int a,b; printf("Enter number a and its power b\n"); scanf("%d%d",&a,&b); printf("a raised to b is %d", foo(a,b)); return 0; } int foo ( int x , int n) { int val=1; if(n>0) { if (n%2 == 1) val = val *x; val = val * foo(x*x , n/2); } return val; } ```