How to implement a user defined recursive function which will update an array in its every call

Hello everyone,

I am trying to implement Shanon Fano Encoding algorithm,

I have created a function shannon() as follows:

    function C(index,col)=shannon(arr,len,i)
    [set1,set2]=partition(arr);
    l1=length(set1);
    l2=length(set2);
    %to assign 0 to set1
    C(1:l1,i)=0;    
    %to assign 1 to set2
    if(l1+1< len)
        C((l1+1):len,i)=1;
    elseif (l1+1== len)
       C(l1+1,i)=1;
    end
    %recursive call on both the sets till the sets are no further divisible
    if(len >1)
        C((1:l1),col)=shannon(set1,l1,i+1);
        C(((l1+1):len),col)=shannon(set2,l2,i+1);
    else
        return
    end
    end

Here, the shannon() function will create a Codeword matrix C(index,col) ,which will store the respective codeword of the symbols using Shannon Fano Coding.

I have defined another user defined function partition() ,which will divide the array of symbols into two nearly equal sum of arrays,

    %Function call:
    C(index,col)=shannon(P,N,1);
    %P is the array (1 x N) storing probabilities of N symbols in descending order
    %1 is the 1st codeword index which needs to be updated/stored in first call of shannon()

but the above program is not syntactically correct

so, can anyone tell me what should be the syntax of shannon() and what needs to be modified in the code so that it will return successfully the Codeword matrix?

I am attaching the main program and partition() function for convenience:

    %Main Program:
    clc
    clear all
    close all
    %Generation of N symbols
    prompt='Enter number of symbols (N): ';
    N=input(prompt);
    P= rand(1,N);
    P= P/ (sum(P));
    P= sort(P,'descend');
    %Calculation of H
    H=0;
    for i=1:N
        H= H+ (-1)*P(i)*log2(P(i));
    end
    %Implementation of the algorithm
    C(index,col)=shannon(P,N,1);
    

partition.m :

    %partition() function:
    function [arr_set1,arr_set2] =partition(arr)
    %User Defined function to divide an array into two nearly equal sums of
    %arrays
        N=length(arr);
        pos1=1;
        pos2=1;
        sum1=0;
        sum2=0;
        f=1;
        l=N;
        while(f<=l)
            if (sum2 < sum1 )
                set2(pos2)=arr(l);
                pos2=pos2+1;
                sum2=sum2 + arr(l);
                l=l-1;
            else
                set1(pos1) = arr(f);
                pos1=pos1 +1;
                sum1 = sum1 + arr(f);
                f=f+1;
            end
        end 
        arr_set1=set1;
        arr_set2= wrev(set2);
    end

Answer 1

[Prudhvi Peddagoni]

Hi,

You can find the implementation of shaannon fano encoding here.

To update an array in the recursive function , you need to pass and return that array like this:

c = zeros(6,1);
a = 6;
c = factorial(c,a);

function c = factorial(c,a)
% c is an vector of size len(a) x 1. we need to compute factorials from 1
% to a and store them in vector c.
if a==1
    c(1) = 1;
else 
   c = factorial(c,a-1);
   c(a) = a*c(a-1);
end
end

Hope this helps.