Backward recursion

Tree 구조가 있을 때 각 노드가 자신의 sub-tree 노드들의 정보를 다 취합해서 갖고 있게 하고 싶을 경우가 있다. 각 노드마다 자신의 child 노드의 수가 몇 개인지 원할 때도 있고 (모든 노드가 +1의 값을 갖게 하면), 혹은 inverse dynamices를 풀 때 사용되는 recursive Newton Euler (RNE)의 inward operation을 할 때가 그렇다. 

%
%                   1
%                  /|\
%                 / | \
%                /  |  \
%               2   3   4
%              / \      |
%             5   6     7
%                      / \
%                     8   9
%
%                 1
%                /
%               2
%              / \
%             5   3
%              \   \
%               6   4
%                  /
%                 7
%                /
%               8
%                \
%                 9
%
ccc

트리 구조는 위와 같이 multiary tree 구조와 left child right sibling tree가 있다고 가정하자. 

% Initialize values
f_vals = rand(1,9);

% Left child right sibling
node_lcrs(1) = struct('child',2,'sister',0,'f',f_vals(1));
node_lcrs(2) = struct('child',5,'sister',3,'f',f_vals(2));
node_lcrs(3) = struct('child',0,'sister',4,'f',f_vals(3));
node_lcrs(4) = struct('child',7,'sister',0,'f',f_vals(4));
node_lcrs(5) = struct('child',0,'sister',6,'f',f_vals(5));
node_lcrs(6) = struct('child',0,'sister',0,'f',f_vals(6));
node_lcrs(7) = struct('child',8,'sister',0,'f',f_vals(7));
node_lcrs(8) = struct('child',0,'sister',9,'f',f_vals(8));
node_lcrs(9) = struct('child',0,'sister',0,'f',f_vals(9));
[~,node_lcrs] = foo_lcrs(node_lcrs,1);

% multiary tree
node_mltr(1) = struct('childs',[2,3,4],  'f',f_vals(1));
node_mltr(2) = struct('childs',[5,6],    'f',f_vals(2));
node_mltr(3) = struct('childs',[],       'f',f_vals(3));
node_mltr(4) = struct('childs',[7],      'f',f_vals(4));
node_mltr(5) = struct('childs',[],       'f',f_vals(5));
node_mltr(6) = struct('childs',[],       'f',f_vals(6));
node_mltr(7) = struct('childs',[8,9],    'f',f_vals(7));
node_mltr(8) = struct('childs',[],       'f',f_vals(8));
node_mltr(9) = struct('childs',[],       'f',f_vals(9));
[f,node_mltr] = foo_mltr(node_mltr,1);

for i_idx = 1:length(node_lcrs)
    fprintf('[%d] lcrs:[%.2f] / mltr:[%.2f]. \n',...
        i_idx,node_lcrs(i_idx).f_sum,node_mltr(i_idx).f_sum);
end

그럼 위와 같이 돌렸을 때, 같은 결과가 나오게 된다. 

[1] lcrs:[5.57] / mltr:[5.57]. 
[2] lcrs:[1.89] / mltr:[1.89]. 
[3] lcrs:[0.42] / mltr:[0.42]. 
[4] lcrs:[2.46] / mltr:[2.46]. 
[5] lcrs:[0.79] / mltr:[0.79]. 
[6] lcrs:[0.96] / mltr:[0.96]. 
[7] lcrs:[1.54] / mltr:[1.54]. 
[8] lcrs:[0.04] / mltr:[0.04]. 
[9] lcrs:[0.85] / mltr:[0.85]. 

먼저 left-child right-sibling tree에서 동작하는 코드는

function [f_out,node_lcrs] = foo_lcrs(node_lcrs,j)
%
% Check how the recursion works 
%
if j == 0
    f_out = 0;
    return
end
f0 = node_lcrs(j).f;
% fprintf('[foo_lcrs] A j:[%d].\n',j);

%% To child
[f1,node_lcrs] = foo_lcrs(node_lcrs,node_lcrs(j).child);
f = f0 + f1;
node_lcrs(j).f_sum = f; % append f
% fprintf('[foo_lcrs] B j:[%d].\n',j);

%% To sister
[f2,node_lcrs] = foo_lcrs(node_lcrs,node_lcrs(j).sister);
% fprintf('[foo_lcrs] C j:[%d].\n',j);
f_out = f + f2;

위와 같고, 좀 더 일반적인 multiary tree에서는 아래와 같은 코드가 같은 동작을 한다. 

function [f,node_mltr] = foo_mltr(node_mltr,j)
%
% Check how the recursion works 
%
if isempty(j)
    f = 0;
    return;
end
f0 = node_mltr(j).f;

%% To child
f = f0;
for child = node_mltr(j).childs % for each child 
    [f1,node_mltr] = foo_mltr(node_mltr,child);
    f = f + f1;
end
node_mltr(j).f_sum = f;