0

Ho do I trace calls made to recursive Fibonacci function without using global variable in matlab. I tried it using global variable but unable to do without using it. This was asked in our course assignment in which we were bound to use recursive algorithm and no use of global variables.

format long;
global ind;
ind=0;

n = input('');
1;function [res] = fib( n )
  global ind;
  if(n==1 || n==2)
     ind = ind+1;
    res=1;
  else
     ind = ind+1;
     res = fib(n-1)+fib(n-2);

  end

end



fprintf('%d %d',fib(n),ind)
Anshul Yadav
  • 13
  • 2
  • 7
  • 1) Why do you want to avoid using global variables? 2) The code does not run (as it is) on my computer – Nicky Mattsson May 03 '18 at 10:50
  • 1
    @NickyMattsson 1) because they are a bad programming practice, specially with names like `ind`! – Ander Biguri May 03 '18 at 11:04
  • 1
    @AnderBiguri, I agree, that one should, of course, keep the number of global variables to an absolute minimum. But as a counter in recursive function calls, if you cannot use it there, then I cannot think of any examples, where they should be used. – Nicky Mattsson May 03 '18 at 11:09
  • @NickyMattsson fair point indeed. If its just an exercise, then you are right, why not use them. – Ander Biguri May 03 '18 at 11:10
  • 1
    @AnderBiguri, There is btw. a rather nice (or at least I like it) discussion of when to use global variables here, https://stackoverflow.com/questions/176118/when-is-it-ok-to-use-a-global-variable-in-c , even though it is technically in C, i think it applies in general. – Nicky Mattsson May 03 '18 at 11:16
  • 1
    If you wrote this as a for loop instead of a recursive function (likely much more efficient that way too) then you don't need to track the counter... Otherwise just have 2 outputs from your function where 1 is the counter and sum the counters as you unravel the recursion. – Wolfie May 03 '18 at 13:35
  • This was our course assignment in which we were forbidden to use global variable. @NickyMattsson This code was originally written on Octave hence it may not work on matlab – Anshul Yadav May 03 '18 at 13:41

1 Answers1

3

If you want to avoid a global variable in a recursive function you can pass in a value that is updated with each successive recursive call.

I don't want to give you the exact solution for your assignment but consider the example for a recursive implementation of the factorial function. It's fairly straightforward to adapt this method to your Fibonacci function.

function [res, call_count] = recursive_factorial(n, call_count)
    % increment counter
    call_count = call_count + 1;
    if n <= 1
        % check for base case
        res = 1;
    else
        % call_count gets updated by recursive call
        [res_prev, call_count] = recursive_factorial(n-1, call_count);
        res = n * res_prev;
    end
end

Usage example of computing 10!. Notice that we initialize the call_count argument to 0 for the initial call.

>> [ten_factorial, call_count] = recursive_factorial(10, 0)
ten_factorial =
    3628800
call_count =
    10

Update

If we were using a global variable call counter then the factorial function would look something like this.

function res = recursive_factorial(n)
    % increment global counter
    global call_count
    call_count = call_count + 1;
    if n <= 1
        res = 1;
    else
        res = n * recursive_factorial(n-1);
    end
end

Compare this with the non-global version and that should help you understand what you need to do to modify your Fibonacci function.

jodag
  • 19,885
  • 5
  • 47
  • 66
  • I know this! Our lecture slides has this example only and we are asked to calculate calls for fibonacci sequence on similar grounds. – Anshul Yadav May 03 '18 at 14:30
  • Try separating `res = fib(n-1)+fib(n-2)` into 3 expressions, then it should be obvious how to implement the call counter. It just needs to be updated at every recursive call. – jodag May 03 '18 at 14:34