How to follow recursion systematically?

Question

Well, I have many 'C language' tests that involve finding the output of a given function,moreover, I need to explain precisely what's the purpose of it. Some of them are recursive functions. And when I meet recursion, I always struggle on finding how to follow it schematically, and even if I do succeed, sometimes I might not understand what is the purpose of the recursive function.

Here are 2 pieces of code:

Main

#include <stdio.h>
#include <conio.h>

int f2(int *a, int n, int x);
int main()
{
  int a[6] = {4, 3, 4, 2};  
  printf("%d\n", f2(a, 4, 5)); 
  getch();
}

f2 function:

int f2(int *a, int n, int x)
{
  if(n>0 && x!=0){
    return (f2(a+1,n-1,x-a[0]) ? 1 : f2(a+1,n-1,x));
  }
  return (x ? 0 : 1);
}

Well, the 'purpose' of the function is to check whether there is a group of numbers in the array that their sum will give x's value. (which is x=5 in this particular example). In this case, it will return true, because 2,3 are inside the array and 2+3=5.

My question is: How can I, on paper, follow it schematically and understand its purpose. Or, how will you guys approach this kind of question? Any help is highly appreciated!!

Answer 1

We had to do this too in school, took forever to write out during exams but it did sort of force understanding.

Basically, you end up with an execution stack, just like the compiler and runtime use behind the scenes to actually execute the code: You start at main, with a certain set of variables. This is the top of the stack. Then main calls f2, pushing that call onto the stack. This new stack frame has different local variables. Write down their values at this frame. Then f2 calls itself, pushing another frame onto the stack (it's the same function, but a different call to it with different arguments). Write down the values again.

When a function returns, pop it off the stack, and write down the return value.

It can help to use indentation to indicate the current stack depth (or just write the whole stack out if you have room). Generally there's only a few variables involved across the entire program invocation, so it makes sense to put them into a table (making it easier to follow what's going on).

A short example:

Stack        |    a    |  n  |  x  | ret
-----------------------------------------
mn               4342     4     5
mn f2            4342     4     5
mn f2 f2          342     3     1
mn f2 f2 f2        42     2    -2
mn f2 f2 f2 f2      2     1    -6
mn f2 f2 f2 f2 f2         0    -8     0
mn f2 f2 f2 f2     (2     1    -6)
mn f2 f2 f2 f2 f2         0    -6     0
mn f2 f2 f2 f2     (2     1    -6)    0
mn f2 f2 f2       (42     2    -2)
...