2.
Pseudocode
S-stack;
A = S[N-1]; //store the last element
B = 0;
call f(S[0..N-2],A,B) //call the function with 0..N-2 stack elements 

function f(S, A, B){
   if(S is empty) return B; //return the value in accumulator, guard.
   
   if(S[-1] == A) //if the last element in the stack equals to the value, stored in A.
         { f(S[0..N-2], S[N-1], B)}
       else
         {f(S[0..N-2], S[N-1], B+S[-1])}
}

Отредактировано ar (2013-10-03 00:10:05)

Все, что может быть записано в виде цикла, может быть тоже представлено в рекурсивной форме. Единственная разница, это, то, что программы в форме записи в виде цикла имеют состояние. В любой момент можно остановить программу и получить промежуточный результат. В рекурсивной форме, из программы не может быть прочитан промежуточный результат (он просто еще не известен). Это называется referential transparency. Это свойство рекурсивной формы является наиважнейшим в функциональном программировании и позволяет избежать многих проблем, связанных с конкурренцией.
Вообще, любая вычислимая функция рекурсивна.
Для построения рекурсивной формы надо подумать о двух вещах:
1. Условие остановки алгоритма
2. Каждый последующий вызов функции должен приближать эту остановку.
В нашем случае 1. это пустой стек. 2. каждый вызов функции вызывается с меньшим стеком.