Как работает множественная рекурсия для одной и той же функции

Question

Может ли кто-нибудь объяснить, как последовательность выполнения этой рекурсии одна за другой работает для функции powerset

static void powerSet(String str, int index, 
            String curr) 

{ 
    int n = str.length(); 
    if (index == n)
    { 
        System.out.println(curr);
        return; 
    } 
    powerSet(str, index + 1, curr + str.charAt(index)); 
    powerSet(str, index + 1, curr);
} 

public static void main(String[] args) 
{
    String str = "abc"; 
        int index = 0;
        String curr="";
    powerSet(str,index,curr); 

    }
} 

Я просмотрел несколько ссылок, но не смог понять

Answer 1

Здесь нет ничего асинхронного, поэтому программа будет ждать завершения каждого вызова, прежде чем перейдет к следующей инструкции. Это означает, что пока он не вернулся из первого внутреннего вызова powerSet, второй не сработает. Конечно, после завершения второго внутреннего вызова от каждой функции есть неявный возврат

Вот шаги, выполняемые вручную; Я вызвал powerSet1 первый внутренний рекурсивный вызов и powerSet2 второй:

main call: powerSet("abc", 0, "");
    powerSet1("abc", 1, "a");
        powerSet1("abc", 2, "ab");
            powerSet1("abc", 3, "abc");
                3===3 => print "abc" and return
            powerSet2("abc", 3, "ab");
                3===3 => print "ab" and return
        powerSet2("abc", 2, "a");
            powerSet1("abc", 3, "ac");
                3===3 => print "ac" and return
            powerSet2("abc", 3, "a");
                3===3 => print "a" and return
    powerSet2("abc", 1, "");
        powerSet1("abc", 2, "b");
            powerSet1("abc", 3, "bc");
                3===3 => print "bc" and return
            powerSet2("abc", 3, "b");
                3===3 => print "b" and return
        powerSet2("abc", 2, "");
            powerSet1("abc", 3, "c");
                3===3 => print "c" and return
            powerSet2("abc", 3, "");
                3===3 => print "" and return

Результат будет следующим (с пустой строкой в ​​конце):

abc
ab
ac
a
bc
b
c

EDIT: вот более подробная версия: имейте в виду, что каждый отступ - это новая функция, вызываемая, которая сохраняет свои значения для index и curr, я оставил вертикальные пунктирные линии, чтобы вы могли легко найти, что было значения для этого уровня. Программа следует за строкой solid:

NOTE: for all recursion levels str="abc" (stays unchanged)

main call: powerSet("abc", 0, "");
 index=0 / curr=""
 |
 └-- powerSet1("abc", 1, "a");
     index=1 / curr="a"
 |   |
     └-- powerSet1("abc", 2, "ab");
 |       index=2 / curr="ab"
     |   |
 |       └-- powerSet1("abc", 3, "abc");
     |       index=3 / curr="abc"
 |       |   |
     |       └-- index==str.length => print "abc" and return -┐
 |       ┌----------------------------------------------------┘
     |   |
 |       └-- powerSet2("abc", 3, "ab");
     |       index=3 / curr="ab"
 |       |   |
     |       └-- index==str.length => print "ab" and return -┐
 |       ┌---------------------------------------------------┘
     |   |
 |       └-- end of function (implicit return) -┐
     ┌------------------------------------------┘
 |   |
     └-- powerSet2("abc", 2, "a");
 |       index=2 / curr="a"
     |   |
 |       └-- powerSet1("abc", 3, "ac");
     |       index=3 / curr="ac"
 |       |   |
     |       └-- index==str.length => print "ac" and return -┐
 |       ┌---------------------------------------------------┘
     |   |
 |       └-- powerSet2("abc", 3, "a");
     |       index=3 / curr="a"
 |       |   |
     |       └-- index==str.length => print "a" and return -┐
 |       ┌--------------------------------------------------┘
     |   |
 |       └-- end of function (implicit return) -┐
     ┌------------------------------------------┘
 |   |
     └-- end of function (implicit return) -┐
 ┌------------------------------------------┘
 |
 └-- powerSet2("abc", 1, "");
     index=1 / curr=""
 |   |
     └-- powerSet1("abc", 2, "b");
 |       index=2 / curr="b"
     |   |
 |       └-- powerSet1("abc", 3, "bc");
     |       index=3 / curr="bc"
 |       |   |
     |       └-- index==str.length => print "bc" and return -┐
 |       ┌---------------------------------------------------┘
     |   |
 |       └-- powerSet2("abc", 3, "b");
     |       index=3 / curr="b"
 |       |   |
     |       └-- index==str.length => print "b" and return -┐
 |       ┌--------------------------------------------------┘
     |   |
 |       └-- end of function (implicit return) -┐
     ┌------------------------------------------┘
 |   |
     └-- powerSet2("abc", 2, "");
 |       index=2 / curr=""
     |   |
 |       └-- powerSet1("abc", 3, "c");
     |       index=3 / curr="c"
 |       |   |
     |       └-- index==str.length => print "c" and return -┐
 |       ┌--------------------------------------------------┘
     |   |
 |       └-- powerSet2("abc", 3, "");
     |       index=3 / curr=""
 |       |   |
     |       └-- index==str.length => print "" and return -┐
 |       ┌-------------------------------------------------┘
     |   |
 |       └-- end of function (implicit return) -┐
     |<-----------------------------------------┘
 |   |
     └-- end of function (implicit return) -┐
 |<-----------------------------------------┘
 |
 └-- end of function (final return)