Сохранение результатов в рекурсивной функции/BST

Question

Я пишу функцию BST, которая будет хранить все ключи в пределах заданного диапазона в виде строки:

String rangeToString(TreeNode root,int low, int high, String result){ 
    if(root==null) return ""; 
    if(root.key>low)) rangeToString(root.leftChild, low, high,result); 
    if(root.key>=low && root.key.<=high) result+=root.key; 
    if(root.key<high) rangeToString(root.rightChild,low,high,result); 
    return result; 

}

Я в основном делаю перемещение по порядку, добавление значений в строку, когда они находятся в зоне действия. В настоящий момент он возвращает строку, содержащую только корневой ключ. Я знаю, что проблема в моих операциях return, но я просто не могу понять, как реализовать функцию без них. Может ли кто-нибудь указать мне в правильном направлении, пожалуйста?

Answer 1

Во-первых, вы, вероятно, хотите включить возврат ваших рекурсии вызовов, так как вы возвращаете результаты ваших рекурсии:

String rangeToString(TreeNode root,int low, int high, String result){ 
    if(root==null) return ""; 
    if(root.key>low)) return rangeToString(root.leftChild, low, high,result); 
    if(root.key>=low && root.key.<=high) result+=root.key; 
    if(root.key<high) return rangeToString(root.rightChild,low,high,result); 
    return result; 
} 

я отношусь с подозрением к вашим условиям, так что я бы потратить некоторое время на изучение тех ... На самом деле, возврат на рекурсии делает предположение о структуре ваших условий.

Кроме того, одним из способов сбора параметров, которые являются довольно интуитивно понятными, является использование рекурсии хвоста и накопление ваших результатов в ваших параметрах.

Вы можете прочитать здесь: http://en.wikipedia.org/wiki/Tail_call

Ключ в том, что вы используете сами свои параметры, чтобы собрать результаты, и когда ваша функция будет сделано, вы возвращаете свои параметры (те, которые накапливают результаты) ,

Answer 2

вы можете перечислить в свои аргументы список «скопированных до сих пор» прокрутки (скажем, вы назовите его curlist). то, когда вы вернетесь, верните это curlist argument + .Add(your found key for this recursion level), и в местах, где вы рекурсивно называете fonction (rangeToString), вы объединяете результат с текущим списком curlist (используя Append или что-то еще).

псевдо-код:

list<string> myRecursiveFunc(some args, list<string> curlist) 
{ 
    if (recursConditionOK) 
     curlist = curlist.Append(myRecusriveFunc, curlist); 
    return curlist; 
}