how does recursive boolean work? | Together C & C++ | Page 1

upper comet Nov 8, 2022, 2:17 PM

#

For example, lets take this simple recursive code that solves coin problem (can you use given array of coins to add up to num)

bool CoinProblem(int targ, vector<int> &nums) 
{
   if (targ == 0)
      return true;
   if(targ < 0)
   return false;  
   for (size_t i = 0; i < size(nums); i++)
   {
      if(CoinProblem(targ - nums[i], nums) == true)
      return true; 
   }
   return false;
}```

potent mesaBOT Nov 8, 2022, 2:17 PM

#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

proven berry Nov 8, 2022, 2:18 PM

#

upper comet For example, lets take this simple recursive code that solves coin problem (can ...

so what part of this is unclear for you?

upper comet Nov 8, 2022, 2:18 PM

#

give me a moment

#

#

after it returns true || false, what will happen to the parent node?

#

for example when fibanocci got to the base case returned integer, it was used, added to each other

#

like fib(3) = fib(2) + fib(1) = 1 + 1 = 2

#

but in this case

#

there are boolean values

proven berry Nov 8, 2022, 2:22 PM

#

well your code doesn't realy have branching

upper comet Nov 8, 2022, 2:22 PM

#

oh wait

proven berry Nov 8, 2022, 2:22 PM

#

it's simply linear recursive calls

upper comet Nov 8, 2022, 2:23 PM

#

so after it returns true on the it simply stops?

proven berry Nov 8, 2022, 2:23 PM

#

#

so this is your call chain

#

bool CoinProblem(int targ, vector<int> &nums) 
{
   if (targ == 0)
      return true;
   if(targ < 0)
   return false;  <-- the chain is ended
   for (size_t i = 0; i < size(nums); i++)
   {
      if(CoinProblem(targ - nums[i], nums) == true)
      return true; <-- the chain is ended
   }
   return false; <-- the chain is ended
}

#

once any return is called it will go to the "parent"

#

and then it will continue in the parent

upper comet Nov 8, 2022, 2:25 PM

#

so if 1 child return true, than it goes to the parent, which wont go for the next child, and return to its parent?

#

same goes for false?

#

oh wait

#

it will work only with true, right?

#

because the first ever called function was to identify if its true or false, and all of next children, will multiply until at least 1 true is met

#

cause when its false, it will continue with other index

upper comet Nov 8, 2022, 2:28 PM

#

proven berry ```cpp bool CoinProblem(int targ, vector<int> &nums) { if (targ == 0) ...

then you are wrong (??)

#

   if(targ < 0)
   return false;  <-- the chain is ended``` cause this will just continue the func, but with other index, next iteration by for

proven berry Nov 8, 2022, 2:29 PM

#

ah sorry I phrased it a bit wrong

#

so what I meant with that is say nums.size() = 0, the loop would never run, or there is no matching index the last return could potentially terminate the chain

#

#include <iostream>
#include <vector>
bool CoinProblem(int targ, std::vector<int> &nums) 
{
   if (targ == 0)
      return true;
   if(targ < 0)
   return false;  
   for (size_t i = 0; i < nums.size(); i++)
   {
      if(CoinProblem(targ - nums[i], nums) == true)
      return true; 
   }
   return false; 
}

int main()
{
  std::vector<int> a{};
  std::cout << CoinProblem(1, a);
}

#

holy shit im being dumb rn

upper comet Nov 8, 2022, 2:33 PM

#

shit happens

#

#include <bits/stdc++.h>
using namespace std;
bool CoinProblem(int targ, vector<int> &nums) 
{
   if (targ == 0)
      return true;
   if(targ < 0)
   return false;  
   for (size_t i = 0; i < size(nums); i++)
   {
      if(CoinProblem(targ - nums[i], nums) == true)
      return true; 
   }
   return false;
}

int main()
{

   int a = 1; 
vector<int> v{}; 
   cout << (CoinProblem(a, v) == true ? "yes" : "no");

   return 0;
}```

upper comet Nov 8, 2022, 2:34 PM

#

upper comet ```cpp #include <bits/stdc++.h> using namespace std; bool CoinProblem(int targ, ...

;compile

lime escarpBOT Nov 8, 2022, 2:34 PM

#

Program Output

no

proven berry Nov 8, 2022, 2:34 PM

#

proven berry ```cpp #include <iostream> #include <vector> bool CoinProblem(int targ, std::vec...

;compile

lime escarpBOT Nov 8, 2022, 2:34 PM

#

Program Output

proven berry Nov 8, 2022, 2:34 PM

#

there we go

#

but yeah as you can see with this super simple example now xD
is that that false could end the recursion

#

what I would reccomend is actually putting this in a proper IDE and stepping in / trough the code

#

and travel up and down a callstack

upper comet Nov 8, 2022, 2:35 PM

#

i did so, but with debugging..

#

and my understanding was like yes, but actually no

upper comet Nov 8, 2022, 2:36 PM

#

proven berry ```cpp bool CoinProblem(int targ, vector<int> &nums) { if (targ == 0) ...

   if(targ < 0)
   return false;  <-- the chain is ended``` but this one still doesnt return false itself

#

(if !(negative) inputs are guaranteed)

proven berry Nov 8, 2022, 2:37 PM

#

upper comet ```cpp if(targ < 0) return false; <-- the chain is ended``` but this one ...

I mean that only does it if targs < 0

upper comet Nov 8, 2022, 2:37 PM

#

so its recursion termination case (you are right)

proven berry Nov 8, 2022, 2:37 PM

#

🤔 well more recursion termination in this case

upper comet Nov 8, 2022, 2:37 PM

#

for the child to return false to the parent, continuing the recursion

proven berry Nov 8, 2022, 2:37 PM

#

generally you have some case to limit the recusion depth

proven berry Nov 8, 2022, 2:37 PM

#

upper comet for the child to return false to the parent, continuing the recursion

yes basically

#

recursion is a bit hard to explain honestly

upper comet Nov 8, 2022, 2:38 PM

#

than it wont end the chain

proven berry Nov 8, 2022, 2:38 PM

#

I mean it could

upper comet Nov 8, 2022, 2:38 PM

#

proven berry recursion is a bit hard to explain honestly

yeah, learning it first time was so hard

proven berry Nov 8, 2022, 2:38 PM

#

it's very dependant on how and where in the loop

#

but I phrased that a bit akward ngl

#

but yeah any return statement means it goes 1 recursion depth back up and contiues there

upper comet Nov 8, 2022, 2:39 PM

#

so the only statements that actually give us answer are the one in, after the for loop

#

but even so

#

#

5 - 4 is false, so it will return false, while 5 - 5 is true, which will return true

#

so when the first child fucks up, than it will go for the next iteration, i + 1?? and afterwards returns true?

#

wow

#

https://tenor.com/view/brain-iq-smart-gif-25368965

Tenor

upper comet Nov 8, 2022, 2:44 PM

#

proven berry and travel up and down a callstack

where it will go for the next index, ignoring falsies, searching only for a true

north delta Nov 8, 2022, 2:48 PM

#

wow

#

but what if you will return CoinProblem(targ - nums[i], nums) ;

#

next nodes will return true and false

#

how will compiler understand it?

#

@upper comet @proven berry

upper comet Nov 8, 2022, 2:50 PM

#

good thoughts

#

maybe thats why solution has func()== true, instead of return func()

proven berry Nov 8, 2022, 2:54 PM

#

upper comet

so in your code you don't realy have branching, atleast in some sense

upper comet Nov 8, 2022, 2:55 PM

#

cause false ones just dont matter at all

proven berry Nov 8, 2022, 2:55 PM

#

yeah, so it's a bit hard to explain honestly

#

   for (size_t i = 0; i < size(nums); i++)
   {
      if(CoinProblem(targ - nums[i], nums) == true)
      return true; 
   }

so say you are at depth zero and nums is of size 3

#

you would have the following possibly:
false,false,true where the 2 falses don't do anything and the last true is seen as true and the parent function returns true as well

upper comet Nov 8, 2022, 3:40 PM

#

proven berry yeah, so it's a bit hard to explain honestly

its fine

upper comet Nov 8, 2022, 3:40 PM

#

proven berry well your code doesn't realy have branching

well you are right ig

#

branches that are false just dont have any value, they just get ignored, so ig no branches

#

nice, thank you man!

#

!solved

#how does recursive boolean work?