Recursion

QUESTION 1:
unsigned int foo(unsigned int n, unsigned int r) {

  if (n  > 0) return (n%r +  foo (n/r, r ));

  else return 0;

}

What is  foo(513, 2)  & foo(345, 10) ?


QUESTION 2:

#include<stdio.h> int fun(int n, int *fg) {    int t, f;    if(n <= 1)    {      *fg = 1;       return 1;    }    t = fun(n-1, fg);    f = t + *fg;    *fg = t;    return f; } int main( ) {   int x = 15;   printf ( "%d\n", fun (5, &x));   getchar();   return 0; }

In the above program, there will be recursive calls till n is not smaller than or equal to 1.

fun(5, &x)
       \
         \
       fun(4, fg)
           \
             \
            fun(3, fg)
                 \
                   \
                   fun(2, fg)
                      \
                        \
                          fun(1, fg)

fun(1, fg) does not further call fun() because n is 1 now, and it goes inside the if part. It changes value at address fg to 1, and returns 1.

Inside fun(2, fg)

t = fun(n-1, fg); --> t = 1
  /* After fun(1, fg) is called, fun(2, fg) does following */
   f = t + *fg;      -->  f = 1 + 1 (changed by fun(1, fg)) = 2
   *fg = t;           --> *fg = 1
  return f (or return 2)

Inside fun(3, fg)

t = fun(2, fg); --> t = 2
  /* After fun(2, fg) is called, fun(3, fg) does following */
   f = t + *fg;       -->  f = 2 + 1 = 3
   *fg = t;            --> *fg = 2
  return f (or return 3)

Inside fun(4, fg)

t = fun(3, fg);   --> t = 3
  /* After fun(3, fg) is called, fun(4, fg) does following */
   f = t + *fg;       -->  f = 3 + 2 = 5
   *fg = t;            --> *fg = 3
   return f (or return 5)

Inside fun(5, fg)

t = fun(4, fg);   -->  t = 5
  /* After fun(4, fg) is called, fun(5, fg) does following */
   f = t + *fg;       -->  f = 5 + 3 = 8
   *fg = t;            --> *fg = 5
   return f (or return 8 )

Finally, value returned by fun(5, &x) is printed, so 8 is printed on the screen