Trójkąt pascala

Mam takie polecenie:

Użytkownik podaje liczbę całkowitą n>0.
Program:

alokuje dwie tablice liczb typu int rozmiaru n+1
używając jedynie tych tablic i pewnej niewielkiej liczby zmiennych zaalokowanych statycznie program oblicza rekurencyjnie n-ty wiersz trójkąta Pascala ( wszystkie symbole dwumianowe z górnym parametrem równym n)
wypisuje obliczone wartości
zwalnia pamięć

Napisałem to, ale iteracyjnie i nie wiem jak to zmienić na rekurencję

#include <stdio.h>
#include <stdlib.h>

/*
int triangle(int n, int i)
{
    if(i==0||i== n) return 1;
    else return triangle(n-1, i-1) + triangle(n-1, i);
}
*/

int main()
{
    int n,i,k;
    int * array_1;
    int * array_2;
  
    scanf("%d",&n);
    
    if(n=='0') printf("%d", 1);
    if(n=='1') printf("%d %d", 1, 1);
    
    array_1 = (int*)calloc(n+1,sizeof(int));
    array_2 = (int*)calloc(n+1,sizeof(int));
    
    array_1[0] = 1;
    array_1[1] = 1;
    k=1;
   
    while(k!=n)
    {
    
        for(i=0; i<=k+1; i++)
        {
        if(i==0)
        {
            array_2[0] = 1;
        }
        else if(i==n)
        {
            array_2[i] = 1;
        }
        else
        {
            array_2[i] = array_1[i] + array_1[i-1];
        }
        }
        
        for(i=0; i<=n; i++)
        {
            array_1[i] = array_2[i];
            array_2[i] = 0;
        }
    
        k++;
    }
    
    for(i=0; i<=n; i++)
    {
        printf("%d ", array_1[i]);
    }
    
    /*for(i=0; i<=n; i++)
    {
        printf("%d\t", triangle(n, i));
    }
    */
    
    free(array_1);
    free(array_2);
    return 0;
}

Przecież Masz tam ukomentowaną wersję rekurencyjną, to:

int triangle(int n, int i)
{
    if(i==0||i== n) return 1;
    else return triangle(n-1, i-1) + triangle(n-1, i);
}

lion137 napisał(a):

Przecież Masz tam ukomentowaną wersję rekurencyjną, to:

int triangle(int n, int i)
{
    if(i==0||i== n) return 1;
    else return triangle(n-1, i-1) + triangle(n-1, i);
}

Ale nie jest to wersja rekurencyjna z zadania. Taka wersja wykonuje pełno niepotrzebnych obliczeń, a do obliczenia n-tego wiersza wystarczy poprzedni wiersz.

Daim123 napisał(a):

lion137 napisał(a):

Przecież Masz tam ukomentowaną wersję rekurencyjną, to:

int triangle(int n, int i)
{
    if(i==0||i== n) return 1;
    else return triangle(n-1, i-1) + triangle(n-1, i);
}

Ale nie jest to wersja rekurencyjna z zadania.

Czy ty wiesz co to jest rekurencja? Bo to jest rozwiązanie rekurencyjne!

Taka wersja wykonuje pełno niepotrzebnych obliczeń, a do obliczenia n-tego wiersza wystarczy poprzedni wiersz.

Zgadza się, bo w tym wypadku rekurencja jest złym wyborem.

MarekR22 napisał(a):

Daim123 napisał(a):

lion137 napisał(a):

Przecież Masz tam ukomentowaną wersję rekurencyjną, to:

int triangle(int n, int i)
{
    if(i==0||i== n) return 1;
    else return triangle(n-1, i-1) + triangle(n-1, i);
}

Ale nie jest to wersja rekurencyjna z zadania.

Czy ty wiesz co to jest rekurencja? Bo to jest rozwiązanie rekurencyjne!

Taka wersja wykonuje pełno niepotrzebnych obliczeń, a do obliczenia n-tego wiersza wystarczy poprzedni wiersz.

Zgadza się, bo w tym wypadku rekurencja jest złym wyborem.

To nie wiem, ja tego zadania nie wymyśliłem.

Czyli prawdopodobnie chodzi Ci o programowanie dynamiczne ;)

Chyba rozwiązałem problem.

#include <stdio.h>
#include <stdlib.h>

void recurse (int k, int n, int *array_1, int *array_2)
{
    int i;
    if(k==n+1) return;

    for(i=1; i<=k+1; i++)
    {
    array_2[i] = array_1[i] + array_1[i-1];
    }
    recurse(k+1, n, array_2, array_1);
    
}

int main()
{
    int n,i,k;
    int * array_1;
    int * array_2;
  
    scanf("%d",&n);
    
    if(n=='0') printf("%d", 1);
    if(n=='1') printf("%d %d", 1, 1);
    
    array_1 = (int*)calloc(n+1,sizeof(int));
    array_2 = (int*)calloc(n+1,sizeof(int));
    
    array_1[0] = 1;
    array_1[1] = 1;
    array_2[0] = 1;
    k=1;
   
    recurse(k, n, array_1, array_2);
    
    if(n%2!=0)
    {
    for(i=0; i<=n; i++)
    {
        printf("%d ", array_1[i]);
    }
    }
    else
    {
        for(i=0; i<=n; i++)
           {
               printf("%d ", array_2[i]);
           }
    }
    
    free(array_1);
    free(array_2);
    return 0;
}

jedna tablica wystarczy

              t
             [30
            ]={1}
           ;main(n
          ,k,a, b){
         puts("1 ");
        for(;n<20;n++
       ){for(b=k=0;k<=
      n;){a=t[k];t[k]=a
     +b;b=a;printf("%d "
    ,t[k++]);}puts("");}}